题意
给出一棵以1为根节点树，求每个节点的子树中到该节点距离<=l的节点的个数
题解
方法1：倍增+差分数组
首先可以很容易的转化问题，考虑每个节点对哪些节点有贡献
即每次对于一个节点，找到其第l个父亲，这个操作可以用倍增在logn时间内完成
找到后将x-y这一段区间都加1，很容易想到用差分数组维护
方法2：主席树
考虑节点x和节点x的子树中的一个节点y，记点x到根节点的距离为dis[x]
若dis[y]-dis[x]<=l则满足条件
将不等式变形可得dis[y]<=dis[x]+l
即对每个点以dis[ ]为权值插入树中，查询时查找比dis[x]+l小的节点个数
这时很容易想到主席树，第一维对dis[x]（维护的前缀也就是查询的答案），第二维对节点编号
又由于先决条件是节点y是在x的子树中的，所以我们应弄出一个dfs序
对于每一个节点，其子树即num[x]-----子树中num[y]的最大值
其次，插入时为避免对之后的节点造成影响，应将dis[]从小到大进行插入
注意到dis数据范围较大考虑对其离散化
还有就是，主席树的题目空间往往不能浪费太多
方法3：左偏树
可以考虑，对于节点x的子树中的一个节点
若x与这个节点的距离>l,那么x的父亲与这个节点的距离也一定>l
所以可以考虑用左偏树来维护
对于每个节点x，枚举它的儿子y，维护一个大根堆
另外，两个点之间的距离可以用dis[1,y]-dis[1,x]表示
**没仔细看题数据是longlong啊。。
代码
方法1：倍增+差分数组
方法2：主席树
uses math;
type re=record
a,b,c,num:int64;
end;
type ree=record
h,t,x:longint;
end;
var
i,j:longint;
now,m,n,c,d,k,l,o,ans,x,tmp:int64;
a,dis:array[..]of re;
f:array[..]of boolean;
num,fa,head,q:array[..]of int64;
p:array[..]of ree;
procedure arr(x,y,z:int64);
begin
inc(l);
a[l].a:=head[x];
a[l].b:=y;
a[l].c:=z;
head[x]:=l;
end;
function dfs(x,y:int64):int64;
var u,v:longint;
begin
f[x]:=false; dis[x].a:=y; dis[x].b:=x;
inc(now); dis[x].num:=now;
u:=head[x]; dfs:=now;
while u<> do
begin
v:=a[u].b;
if f[v] then dfs:=max(dfs,dfs(v,y+a[u].c));
u:=a[u].a;
end;
dis[x].c:=dfs;
end;
procedure swap(var x,y:re);
var tmp:re;
begin
tmp:=x; x:=y; y:=tmp;
end;
procedure qsort(h,t:int64);
var i,j,mid:int64;
begin
i:=h; j:=t; mid:=dis[(h+t) div ].a;
repeat
while dis[i].a<mid do inc(i);
while dis[j].a>mid do dec(j);
if i<=j then
begin
swap(dis[i],dis[j]);
inc(i); dec(j);
end;
until i>j;
if i<t then qsort(i,t);
if h<j then qsort(h,j);
end;
procedure build(x,h,t:int64);
var mid:int64;
begin
p[x].h:=x*; p[x].t:=x*+; now:=max(now,x*+);
if h=t then exit;
mid:=(h+t) div ;
build(x*,h,mid); build(x*+,mid+,t);
end;
function find(x:int64):int64;
var h,t,mid:int64;
begin
h:=; t:=n;
while h<t do
begin
mid:=(h+t) div +;
if dis[mid].a<=x then h:=mid else t:=mid-;
end;
exit(h);
end;
procedure insert(pre,x,h,t:int64);
var tmp,mid:longint;
begin
inc(now); p[now]:=p[pre]; inc(p[now].x); tmp:=now;
if h=t then exit;
mid:=(h+t) div ;
if (x<=mid) then
begin
insert(p[now].h,x,h,mid);
p[tmp].h:=tmp+;
end else
begin
insert(p[now].t,x,mid+,t);
p[tmp].t:=tmp+;
end;
end;
function query(x,h1,t1,h,t:int64):int64;
var mid:int64;
begin
if (h>t1) or (t<h1) then exit();
if (h<=h1) and (t1<=t) then exit(p[x].x);
mid:=(h1+t1) div ;
exit(query(p[x].h,h1,mid,h,t)+query(p[x].t,mid+,t1,h,t));
end;
begin
readln(n,k); fillchar(f,sizeof(f),true);
for i:= to n- do
begin
read(c,d); arr(i+,c,d); arr(c,i+,d);
end;
dfs(,);
qsort(,n); o:=;
for i:= to n do
begin
if (i=) or (dis[i].a<>dis[i-].a) then
inc(o);
num[i]:=o;
end;
now:=; build(,,n);
fa[]:=;
for i:= to n do
begin
if (i<>) and (num[i]=num[i-]) then
begin
tmp:=now;
insert(fa[num[i]],dis[i].num,,n);
fa[num[i]]:=tmp+;
end
else
begin
fa[num[i]]:=now+;
insert(fa[num[i]-],dis[i].num,,n);
end;
end;
for i:= to n do
begin
x:=find(dis[i].a+k);
ans:=query(fa[num[x]],,n,dis[i].num,dis[i].c);
q[dis[i].b]:=ans;
end;
for i:= to n do writeln(q[i]);
end.
方法3：左偏树
type re=record
a,b,c:int64;
end;
var
i,j:longint;
m,n,ans,l,c,d:int64;
k:int64;
f:array[..]of boolean;
a:array[..]of re;
dis,left1,right1,fa,cnt,ll,head,vv,num:array[..]of int64;
procedure arr(x,y,z:int64);
begin
inc(l);
a[l].a:=head[x];
a[l].b:=y;
a[l].c:=z;
head[x]:=l;
end;
function getfa(x:int64):int64;
begin
while (fa[x]<>) do x:=fa[x];
exit(x);
end;
procedure swap(var x,y:int64);
var tmp:int64;
begin
tmp:=x; x:=y; y:=tmp;
end;
function merge(x,y:int64):int64;
var tmp:int64;
begin
if (x=) or (y=) then exit(x+y);
if (dis[x]<dis[y]) then swap(x,y);
right1[x]:=merge(right1[x],y);
fa[right1[x]]:=x;
if (ll[left1[x]]<ll[right1[x]]) then swap(left1[x],right1[x]);
ll[x]:=ll[right1[x]]+; cnt[x]:=cnt[left1[x]]+cnt[right1[x]]+;
exit(x);
end;
function delete(x:int64):int64;
var tmp:int64;
begin
fa[left1[x]]:=; fa[right1[x]]:=;
if left1[x]<> then tmp:=left1[x] else tmp:=right1[x];
merge(left1[x],right1[x]);
exit(getfa(tmp));
end;
procedure dfs(x,y:int64);
var u,v,c,d,goal,ans,z:int64;
begin
ans:=; f[x]:=false; dis[x]:=y;
u:=head[x];
while u<> do
begin
v:=a[u].b;
if f[v] then
begin
dfs(v,y+a[u].c);
c:=getfa(v); goal:=y+k;
while (c<>) and (dis[c]>goal) do
begin
c:=delete(c);
end;
if c<> then
begin
ans:=ans+cnt[c];
z:=getfa(x);
merge(z,c);
end;
end;
u:=a[u].a;
end;
if k>= then vv[x]:=ans+ else vv[x]:=ans;
end;
begin
readln(n,k);
if k< then writeln('');
for i:= to n- do
begin
read(c,d); arr(i+,c,d); arr(c,i+,d);
end;
for i:= to n do cnt[i]:=;
fillchar(f,sizeof(f),true);
dfs(,);
for i:= to n do writeln(vv[i]);
end.