考虑当前点i只对往上一条链有贡献，就dfs保存到当前点之上的所有父亲点，二分查找到哪个点停住，差分维护。

我们从根结点出发，dfs整棵树，在dfs的过程中，我们维护一个道路长度的和sum[]，sum[j]就是1到第j个城市的路径之和。

假如我们现在dfs到了第j个城市v，此时1~j的路径之和就是sum[j],然后sum[j]-x[v]就是从v城市出发所能到达的最远距离。

int pos=lower_bound(sum,sum+ret+1,sum[ret]-x[v])-sum;

接下来二分查找计算出从v出发在这条路径上所能到达的最远的城市。它所能到达的城市都需要+1。

最后把子节点的个数加到父节点上即可。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e6+10;
int head[maxn],cnt;
struct node {
    int to,w,nxt;
}e[maxn];
int n,d[maxn],sum[maxn],ans[maxn],id[maxn],tot;
void addage( int u, int v, int w )
    e[cnt].to = v;
    e[cnt].w = w;
    e[cnt].nxt = head[u];
    head[u] = cnt++;
void dfs( int u, int fa )
    for ( int i=head[u]; i!=-1; i=e[i].nxt ) {
        int v = e[i].to, w=e[i].w;
        if ( v==fa ) continue ;
        sum[tot] = sum[tot-1] + w;
        id[tot] = v;
        int pos = lower_bound(sum,sum+tot,sum[tot]-d[v]) - sum;
        if ( pos<tot ) {
            ans[ u ] ++;
            ans[ id[pos-1] ] --;
        tot ++;
        dfs(v,u);
        tot --;
        ans[u] += ans[v];
signed main()
    freopen("car.in","r",stdin);
    int t;cin>>t;
    while ( t-- ) {
        memset(head,-1,sizeof(head));cnt=0;
        memset(ans,0,sizeof(ans));
        cin >> n;
        for ( int i=1; i<=n; i++ ) scanf("%lld",&d[i]);
        for ( int i=1; i<n; i++ ) {
            int u,v,w;scanf("%lld %lld %lld",&u,&v,&w);
            addage(u,v,w);addage(v,u,w);
        sum[0]=0; id[0]=1;
        tot = 1;
        dfs(1,1);
        for ( int i=1; i<n; i++ ) printf("%lld ",ans[i]);
        printf("%lld\n",ans[n]);
    return 0;
Whistle has bought a new car, which has an infinite fuel tank capacity.
He discovered an irregular country since it has n cities and there are exactly n - 1roads between them, of course
给出一棵有向树，有点权和边权，定义一个节点i的答案为以i为根的子树中有多少j的点权不小于j->i的简单路径上边权和，求所有点的答案 
Input 
第一行一整数T表示用例组数，每组用例首先输入树上点数n，之后n个整数x[i]表示第i个点的点权，最后n-1行每行三个整数u,v,w表示树上一条边u-v的边权是w，树根是1(1<=n<=5e5,1<=x[i],w<=1e9) 
　　给出一颗有点权和边权的树。求每一个点u的子树中有多少点v，使得点v到点u的距离小于等于点v的权值。
　　对于每一个点，倍增的预处理出他的祖宗节点及距离。根据预处理的结果求出每个点能到的最远的祖宗节点。
　　设点u能到的最远祖宗节点为v。利用差分的思想在点tree[u]+1，点tree[v]-1。
　　最后每个点的答案就是子树的tree[]和。
#includ...
                                    题意：有一棵以1为root，n个节点的根树，然后存在一个有n个数字的数组x，询问从i节点最多走x[i]x[i]x[i]步可以最多到达几个父亲上的点，然后数组n个数字，分别为从1,2,…n1, 2, \dots n1,2,…n出发可以最多到达几个点。
首先我们定义dep[i]dep[i]dep[i]为从根节点得到iii节点的距离。
我们考虑如果从iii点出发的话那么如果它可以到达jjj点那...