LuoguP3066

先吐槽一下,这道题名字好长啊
一个非常明显的思路,利用倍增数组不断向上跳.直到数值大于\(L\),然后直接差分统计答案就好了.
这种ZROI也考过,不多赘述了.
我们来考虑主席树做法
我们设\(d_x\)为\(x\)点到跟的距离
让我们求满足\(d_v - d_u<= L,v\in Son_u\)的\(v\)的数量
转化一下式子就变成了
\(d_v <= d_u + L\)
即统计子树内有多少小于等于\(d_u+L\)的数
我们利用dfs序
将每个子树转化为一个区间
然后利用主席树查询.
注意一个小细节
因为我们的数组经过离散化
因此我们就定位数组中第一个大于\(d_u + L\)的数,来查询对应区间内有多少数严格小于它就好了
因此在离散化完成数组最后加入一个\(\infty\)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#define LL long long
using namespace std;
const int N = 2e5 + 3;
int L[N],R[N];
struct node{
    int sum;
    int lc,rc;  
}a[N << 5];
struct edge{
    int to;
    int nxt;
    LL data;
}e[N << 1];
LL v[N],b[N];
int rt[N],head[N];
int n,tot = 1,t,cnt;LL g;
inline LL read(){
    LL v = 0,c = 1;char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') c = -1;
        ch = getchar(); 
    }
    while(isdigit(ch)){
        v = v * 10 + ch - 48;
        ch = getchar(); 
    }
    return v * c;   
}
inline void add(int x,int y,LL z){
    e[++tot].to = y;
    e[tot].data = z;
    e[tot].nxt = head[x];
    head[x] = tot;
}
inline void dfs(int x,int f,LL dis){
    ++cnt;
    b[cnt] = v[cnt] = dis;
    L[x] = cnt;
    for(int i = head[x];i;i = e[i].nxt){
        int y = e[i].to;
        if(y == f) continue;
        dfs(y,x,dis + e[i].data);
    }
    R[x] = cnt;
}
inline void ins(int &u,int l,int r,int x){
    a[++t] = a[u];
    u = t;
    if(l == r){
        a[u].sum++;
        return ;    
    }
    int mid = (l + r) >> 1;
    if(x <= mid) ins(a[u].lc,l,mid,x);
    else ins(a[u].rc,mid + 1,r,x);
    a[u].sum = a[a[u].lc].sum + a[a[u].rc].sum;
}
inline int query(int u1,int u2,int l,int r,int x){
    if(r < x) return a[u2].sum - a[u1].sum;
    if(l >= x) return 0;
    int mid = (l + r) >> 1;
    if(x <= mid) return query(a[u1].lc,a[u2].lc,l,mid,x);
    else return query(a[u1].rc,a[u2].rc,mid + 1,r,x) + a[a[u2].lc].sum - a[a[u1].lc].sum;
}
int main(){
    n = read(),g = read();
    for(int i = 2;i <= n;++i){
        int x = read();LL z = read();
        add(i,x,z);
        add(x,i,z);
    }
//  cout << 1 << endl;
    dfs(1,0,0);
    sort(b + 1,b + n + 1);
    b[0] = unique(b + 1,b + n + 1) - b - 1;
    for(int i = 1;i <= cnt;++i){
        rt[i] = rt[i - 1];
        v[i] = lower_bound(b + 1,b + b[0] + 1,v[i]) - b;
        ins(rt[i],1,b[0],v[i]);
    }
    b[b[0] + 1] = 1e18 + 7;
    for(int i = 1;i <= n;++i){
        LL k = b[v[L[i]]] + g;
        k = upper_bound(b + 1,b + b[0] + 2,k) - b;
        printf("%d\n",query(rt[L[i] - 1],rt[R[i]],1,b[0],k));   
    }
    return 0;
}