给出一棵树，对于每个叶子节点(x)，求：在所有的树链剖分方案中，求包含(x)的链的最优排名（长度从大到小排序，排名越靠前越优）。
(nle 10^6)
考虑求出一个叶子(x)的答案。首先显然要划分出(rt o x)，记这条链的长度为(L)。
定义(len_i)表示从(i)子树中延伸上去的链长（包括(i)到父亲那段），(mx_i)为(i)子树中的最长链。
假如希望(x)能排到rank1，可以如此贪心：做到某个不被链(rt o x)经过的子树(u)时，对于所有(vin son(u))，尝试找到最小的(len_v)并接在边((u,fa_u))下方。如果一直可以满足(len_ule L)，那么确实可以排到rank1。在做的过程中，如果出现了一次(len_u>L)，那么就让它直接向上延伸到和(rt o x)相交为止。
整理一下思路，可以发现其实就是求：在(rt o x)以外的子树中，极小的满足(mx_u>L)的子树(u)的个数。另外可以发现对于任意(uin rt o x)，(len_ule L)，所以都不可能是极小的(u)。所以可以把范围从(rt o x)以外的子树变成所有的子树。
于是按照询问的叶子深度排序，每次只保留(mx_u>L)的点，此时的叶子个数就是答案。
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
#define N 1000005
#define ll long long
#define INF 1000000000000000
int n,m;
char str[N][13];
struct EDGE{
int to,w;
EDGE *las;
} e[N];
int ne;
EDGE *last[N];
int deg[N];
void link(int u,int v,int w){
e[ne]={v,w,last[u]};
last[u]=e+ne++;
deg[u]++;
}
int fa[N];
ll dep[N],len[N],mx[N];
int in[N],out[N],cnt;
void dfs(int x){
// in[x]=++cnt;
if (x>m){
mx[x]=len[x]=0;
// out[x]=cnt;
return;
}
len[x]=INF;
for (EDGE *ei=last[x];ei;ei=ei->las){
dep[ei->to]=dep[x]+ei->w;
fa[ei->to]=x;
dfs(ei->to);
len[ei->to]+=ei->w;
mx[ei->to]=max(mx[ei->to],len[ei->to]);
len[x]=min(len[x],len[ei->to]);
mx[x]=max(mx[x],mx[ei->to]);
}
// out[x]=cnt;
}
int p[N];
bool cmpp(int a,int b){return dep[a+m]<dep[b+m];}
int q[N],nq;
int cmpq(int a,int b){return mx[a]>mx[b];}
int ans[N];
void cut(ll L){
while (nq){
int x=q[0];
if (mx[x]>L) return;
pop_heap(q,q+nq--,cmpq);
if (fa[x]){
int y=fa[x];
if (--deg[y]==0){
q[nq++]=y;
push_heap(q,q+nq,cmpq);
}
}
}
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d",&n,&m);
for (int i=1,x,w;i<=n;++i){
scanf("%s%d%d",str[i],&x,&w);
link(x,i+m,w);
}
for (int i=1,x,w;i<=m;++i){
scanf("%d%d",&x,&w);
link(x,i,w);
}
dfs(0);
for (int i=1;i<=n;++i)
p[i]=i;
sort(p+1,p+n+1,cmpp);
for (int i=0;i<=m+n;++i)
if (deg[i]==0)
q[nq++]=i;
make_heap(q,q+nq,cmpq);
for (int i=1;i<=n;++i){
cut(dep[p[i]+m]);
ans[p[i]]=nq;
}
for (int i=1;i<=n;++i)
printf("%s %d
",str[i],ans[i]+1);
return 0;
}