口胡$Dsu$ $On$ $Tree$

实际上我懒得写这篇博客的，只是“我不做人（指鸽子）啦”……

重点是轻重链剖分，复杂度不会证，懒得证，看一下这个神仙的吧

所以算法流程是先跑一遍轻儿子（这一步是在算(TA)们的答案，不要误解了），然后消除其的影响

再跑重儿子，不消除影响，再暴力遍历轻儿子统计答案即可。

(CF208E)

板子题，唯一的转化就是将某个点的(k)级祖先的(k)级子孙转化为这个点(k)级祖先的子树中和它在该联通块中深度相同的点。

#include<bits/stdc++.h>
using namespace std;
inline int read()
{
    int f=1,w=0;char x=0;
    while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();}
    while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();}
    return w*f;
}
const int N=100001;
int num_edge,n,q,Cnt;
vector<pair<int,int> > Q[N];
struct Edge{int next,to;} edge[N<<1];
int ans[N],Max[N],Dep[N],f[N],Vis[N];
int head[N<<1],las[N][21],Bet[N],Siz[N];
inline void Add(int from,int to)
{
	edge[++num_edge].next=head[from];
	edge[num_edge].to=to;
	head[from]=num_edge;
}
inline void Dfs_For_Pre(int pos,int fth)
{
	las[pos][0]=fth;Siz[pos]=1;Dep[pos]=Dep[fth]+1;
	for(int i=0;i<=19;i++) las[pos][i+1]=las[las[pos][i]][i];
	for(int i=head[pos];i;i=edge[i].next)
	{
		Dfs_For_Pre(edge[i].to,pos);
		Siz[pos]+=Siz[edge[i].to];
		if(Siz[edge[i].to]>=Siz[Max[pos]]) Max[pos]=edge[i].to;
	}
}
inline void Update(int pos,int Val)
{
	f[Dep[pos]]+=Val;
	for(int i=head[pos];i;i=edge[i].next)
		if(!Vis[edge[i].to]) Update(edge[i].to,Val);
}
inline void Dsu_On_Tree(int pos,int Jud)
{
	for(int i=head[pos];i;i=edge[i].next)
		if(edge[i].to!=Max[pos]) Dsu_On_Tree(edge[i].to,0);
	if(Max[pos]) Dsu_On_Tree(Max[pos],1),Vis[Max[pos]]=1;Update(pos,1);
	for(int i=0;i<(int)Q[pos].size();i++)ans[Q[pos][i].first]=f[Q[pos][i].second]-1;
	Vis[Max[pos]]=0;if(!Jud) Update(pos,-1);
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("A.in","r",stdin);
#endif
	n=read();
	for(int i=1,x;i<=n;i++)
	{
		x=read();
		if(x) Add(x,i);
		else Bet[++Cnt]=i;
	}
	for(int i=1;i<=Cnt;i++) Dfs_For_Pre(Bet[i],0);
	//for(int i=2,x;i<=n;i++) x=read(),Add(x,i);
	q=read();//Dfs_For_Pre(1,0);
	for(int i=1;i<=q;i++)
	{
		int x=read(),k=read(),dep=Dep[x];
		for(int j=20;j>=0;j--) if(k&(1<<j)) x=las[x][j];
		Q[x].push_back(make_pair(i,dep));
	}
	for(int i=1;i<=Cnt;i++) Dsu_On_Tree(Bet[i],0);
	//Dsu_On_Tree(1,0);
	for(int i=1;i<=q;i++) printf("%d ",ans[i]);
	return 0;
}