题意
给出一棵以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[1..500000]of re; f:array[1..500000]of boolean; num,fa,head,q:array[0..500000]of int64; p:array[0..5000000]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<>0 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 2].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*2; p[x].t:=x*2+1; now:=max(now,x*2+1); if h=t then exit; mid:=(h+t) div 2; build(x*2,h,mid); build(x*2+1,mid+1,t); end; function find(x:int64):int64; var h,t,mid:int64; begin h:=1; t:=n; while h<t do begin mid:=(h+t) div 2+1; if dis[mid].a<=x then h:=mid else t:=mid-1; 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 2; if (x<=mid) then begin insert(p[now].h,x,h,mid); p[tmp].h:=tmp+1; end else begin insert(p[now].t,x,mid+1,t); p[tmp].t:=tmp+1; end; end; function query(x,h1,t1,h,t:int64):int64; var mid:int64; begin if (h>t1) or (t<h1) then exit(0); if (h<=h1) and (t1<=t) then exit(p[x].x); mid:=(h1+t1) div 2; exit(query(p[x].h,h1,mid,h,t)+query(p[x].t,mid+1,t1,h,t)); end; begin readln(n,k); fillchar(f,sizeof(f),true); for i:=1 to n-1 do begin read(c,d); arr(i+1,c,d); arr(c,i+1,d); end; dfs(1,0); qsort(1,n); o:=0; for i:=1 to n do begin if (i=1) or (dis[i].a<>dis[i-1].a) then inc(o); num[i]:=o; end; now:=0; build(1,1,n); fa[0]:=1; for i:=1 to n do begin if (i<>1) and (num[i]=num[i-1]) then begin tmp:=now; insert(fa[num[i]],dis[i].num,1,n); fa[num[i]]:=tmp+1; end else begin fa[num[i]]:=now+1; insert(fa[num[i]-1],dis[i].num,1,n); end; end; for i:=1 to n do begin x:=find(dis[i].a+k); ans:=query(fa[num[x]],1,n,dis[i].num,dis[i].c); q[dis[i].b]:=ans; end; for i:=1 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[1..1000000]of boolean; a:array[1..1000000]of re; dis,left1,right1,fa,cnt,ll,head,vv,num:array[0..1000000]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]<>0) 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=0) or (y=0) 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]]+1; cnt[x]:=cnt[left1[x]]+cnt[right1[x]]+1; exit(x); end; function delete(x:int64):int64; var tmp:int64; begin fa[left1[x]]:=0; fa[right1[x]]:=0; if left1[x]<>0 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:=0; f[x]:=false; dis[x]:=y; u:=head[x]; while u<>0 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<>0) and (dis[c]>goal) do begin c:=delete(c); end; if c<>0 then begin ans:=ans+cnt[c]; z:=getfa(x); merge(z,c); end; end; u:=a[u].a; end; if k>=0 then vv[x]:=ans+1 else vv[x]:=ans; end; begin readln(n,k); if k<0 then writeln('111'); for i:=1 to n-1 do begin read(c,d); arr(i+1,c,d); arr(c,i+1,d); end; for i:=1 to n do cnt[i]:=1; fillchar(f,sizeof(f),true); dfs(1,0); for i:=1 to n do writeln(vv[i]); end.