题意

给出以1号点为根的一棵有根树，问每个点的子树中与它距离小于等于l的点有多少个。

题解

左偏树裸题。。
太久没写，来复习一下模板

CODE:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL N=200005;
LL n,l;
struct qq
{LL x,y,z,last;
}e[N];LL num,last[N];
void init (LL x,LL y,LL z)
{num++;e[num].x=x;e[num].y=y;e[num].z=z;e[num].last=last[x];last[x]=num;
}
LL ans[N];
LL dep[N];
LL s1[N],s2[N];
LL v[N],c[N];
LL rt[N];
LL d[N];
LL bt (LL x)
{v[++num]=x;c[num]=1;s1[num]=s2[num]=d[num]=0;return num;
}
LL Merge (LL x,LL y)//两个节点合并 
{if (x==0||y==0) return x+y;if (v[x]<v[y]) swap(x,y);//大根堆 s2[x]=Merge(s2[x],y);c[x]=c[s1[x]]+c[s2[x]]+1;if (d[s2[x]]>d[s1[x]]) swap(s1[x],s2[x]);d[x]=d[s2[x]]+1;return x;
}
void dfs (LL x)
{rt[x]=bt(dep[x]);for (LL u=last[x];u!=-1;u=e[u].last){LL y=e[u].y;dep[y]=dep[x]+e[u].z;dfs(y);rt[x]=Merge(rt[x],rt[y]);while (v[rt[x]]>dep[x]+l)   {rt[x]=Merge(s1[rt[x]],s2[rt[x]]);}}ans[x]=c[rt[x]];
}
int main()
{num=0;memset(last,-1,sizeof(last));scanf("%lld%lld",&n,&l);for (LL u=2;u<=n;u++){LL x,z;scanf("%lld%lld",&x,&z);init(x,u,z);}num=0;dep[1]=1;dfs(1);for (LL u=1;u<=n;u++) printf("%lld\n",ans[u]);return 0;
}