TLE #2 #6 #8 #9 #10

#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int INF=0x3f3f3f3f;
const int N=401100;

inline long long read()
{
	long long f=1,x=0; char ch=getchar();
	while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }
	while(isdigit(ch))  { x=x*10+ch-'0';    ch=getchar(); }
	return f*x;
}

#define mid (l+r>>1)
#define iL T[i].ls
#define iR T[i].rs
struct tree
{
    int ls,rs;
    int val;
}T[N<<6];
struct edge
{
    int next,to;
    long long dis;
}e[N<<1];
int root[N],cnt;
int head[N],tot;
int n,top,ans[N];
long long tmp;
long long depL[N],depR[N];
long long NUM[N<<1];

void add_edge(int from,int to,long long dis)
{
    e[tot].next=head[from];
    e[tot].to=to;
    e[tot].dis=dis;
    head[from]=tot++;
}

void pushup(int i)
{ T[i].val=T[iL].val+T[iR].val; }

void updata(int &i,int l,int r,int p,int num)
{
    if(!i) i=++cnt;
    if(l==r) return (void)(T[i].val+=num);
    if(p<=mid) updata(iL,l,mid,p,num);
    if(p>mid)  updata(iR,mid+1,r,p,num);
    pushup(i);
}

int query(int i,int l,int r,int L,int R)
{
    if(!i) return 0;
    if(L<=l&&r<=R) return T[i].val;
    int sum=0;
    sum+=query(iL,l,mid,L,R);
    sum+=query(iR,mid+1,r,L,R);
    return sum;
}

void Merge(int &i,int j,int l,int r)
{
    if(!i||!j) return (void)(i+=j);
    if(l==r)   return (void)(T[i].val+=T[j].val);
    Merge(T[i].ls,T[j].ls,l,mid);
    Merge(T[i].rs,T[j].rs,mid+1,r);
    pushup(i);
}

void GetDeep(int u,int dep)
{
    //root[u]=u;
    NUM[++top]=(depL[u]=dep);
    NUM[++top]=(depR[u]=dep+tmp);
    for(int i=head[u];~i;i=e[i].next)
     GetDeep(e[i].to,dep+e[i].dis);
}

void dfs(int u)
{
    if(!u) return ;
    updata(root[u],0,top,depL[u],1);
    for(int i=head[u],v;~i;i=e[i].next)
    {
        dfs(v=e[i].to);
        Merge(root[u],root[v],0,top);
    }
    ans[u]=query(root[u],0,top,depL[u],depR[u]);
}

signed main()
{
    	memset(head,-1,sizeof(head));
    n=read(); tmp=read();
    for(int i=2;i<=n;i++)
    {
        int fa=read(),w=read();
        add_edge(fa,i,w);
    }
    GetDeep(1,0);
    sort(NUM+1,NUM+top+1);
    top=unique(NUM+1,NUM+top+1)-NUM-1;
    for(int i=1;i<=n;i++)
    {
        depL[i]=lower_bound(NUM+1,NUM+top+1,depL[i])-NUM;
        depR[i]=lower_bound(NUM+1,NUM+top+1,depR[i])-NUM;
    }
    dfs(1);
    for(int i=1;i<=n;i++)
     printf("%d\n",ans[i]);
	return 0;
}