网上题解似乎都是可并堆。

这题可以给每个点自己+1,上面第一个距离>=l的祖先-1，然后统计子树和，即为答案。

求那个祖先可以dfs一遍，把点存在栈里，然后二分。

$O(nlogn)$

能拿bzoj rank1。

#include<cstdio>
using namespace std;

typedef long long ll;
#define pb push_back
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)

template <typename T> inline void chmin(T &x,const T &y)
{
    if(x>y)x=y;
}
template <typename T> inline void chmax(T &x,const T &y)
{
    if(x<y)x=y;
}

const int ch_top=1e7;
char ch[ch_top],*now_r=ch-1,*now_w=ch-1;
#define gc (*++now_r)
#define c *now_r
void read(int &x)
{
    while(gc<'0');
    x=c-'0';
    while(gc>='0')x=x*10+c-'0';
}
void read(ll &x)
{
    while(gc<'0');
    x=c-'0';
    while(gc>='0')x=x*10+c-'0';
}
#undef gc
#undef c
void write(int x)
{
    static char st[20];
    int top=0;
    do{st[++top]='0'+x%10;}while(x/=10);
    do{*++now_w=st[top];}while(--top);
    *++now_w='\n';
}

const int N=2e5+5;
int n,t[N],nex[N];
ll l,a[N];
ll st[N];int stx[N],top;
int s[N];
void find(const ll &ns,int r)//将第一个<=ns的祖先-1 
{
    int l=1;
    if(st[r]<=ns){--s[stx[r]];return ;}
#define mid (l+r>>1)
    while(l+1!=r)
    if(st[mid]<=ns)l=mid;
    else r=mid;
    --s[stx[l]];
}
void dfs(int x,const ll &ns,int dep)
{
    st[dep]=ns;stx[dep]=x;
    if(ns>=l)
    {
        find(ns-l,dep-1);
    }
    s[x]=1;
    for(int y=t[x];y;y=nex[y]) 
    {
      dfs(y,ns+a[y],dep+1);
      s[x]+=s[y];
    }
}

int main()
{
    freopen("1.in","r",stdin);//freopen("1.out","w",stdout);
    ch[fread(ch,1,ch_top,stdin)]=0;
    read(n);read(l);l+=1;
    rep(i,2,n)
    {
        int x;
        read(x);read(a[i]);
        nex[i]=t[x];t[x]=i;        
    }
    dfs(1,0,1);
    rep(i,1,n)write(s[i]);
    fwrite(ch,1,now_w-ch+1,stdout);
}