这题的在线做法好少啊，我来贡献个可持久化线段树的题解吧。

前置知识

• 可持久化数组；
• 树上 k 级祖先，不用会长链剖分的解法，这题倍增够用了；
• 获得一棵树的 dfs 序。

进入正题

拿到森林后，我们先通过一遍 dfs 处理出倍增数组并得到 dfs 序，在 dfs 序上建立主席树，主席树内存每个点的深度。

dfs 序的性质：一颗子树的 dfs 序连续。

通过这个性质，在我们找到 k 级祖先后，我们可以将原问题转化为，在一棵子树内，有多少点深度与询问点相同。显然，主席树完全可以胜任，懒得写主席树的可以写分块，也能过。

代码

思路讲的很清楚了，上代码：

#include<cstdio>
int n,m,rt[100010],head[100010],to[200010],nxt[200010],cnt,dfn[100010],rk[100010],f[100010][22],d[100010],bel[100010],sz[100010];
void add(int const &x,int const &y){
	to[++cnt]=y,nxt[cnt]=head[x],head[x]=cnt;
}
void dfs(int const &x,int const &fa){
	bel[x]=bel[fa],dfn[x]=++cnt,sz[x]=1,d[x]=d[fa]+1,f[x][0]=fa,rk[cnt]=x;
	for(int i=1;i<=20;i++)f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nxt[i])
		if(to[i]!=fa)
			dfs(to[i],x),sz[x]+=sz[to[i]];
}
struct node{
	int v,ls,rs;
}tr[4000010];
inline void clone(int &x){tr[++cnt]=tr[x],x=cnt;}
void update(int const &p,int &x,int const &l=1,int const &r=n){
	clone(x);
	tr[x].v++;
	if(l==r) return;
	int mid=(l+r)>>1;
	if(p<=mid) update(p,tr[x].ls,l,mid);
	else update(p,tr[x].rs,mid+1,r);
}
int query(int const &p,int const &x1,int const &x2,int const &l=1,int const &r=n){
	if(l==r) return tr[x1].v-tr[x2].v;
	int mid=(l+r)>>1;
	if(p<=mid) return query(p,tr[x1].ls,tr[x2].ls,l,mid);
	else return query(p,tr[x1].rs,tr[x2].rs,mid+1,r);
}
int main(){
	scanf("%d",&n);
	for(int i=1,x;i<=n;i++)scanf("%d",&x),add(x,i);
	cnt=0;
	for(int i=1;i<=n;i++)if(!bel[i])bel[0]=i,dfs(i,0);
	bel[0]=cnt=0;
	for(int i=1;i<=n;i++)update(d[rk[i]],rt[i]=rt[i-1]);
	scanf("%d",&m);
	while(m--){
		int x,k,p;
		scanf("%d%d",&x,&k);
		if(d[x]<=k){printf("0 ");continue;}
		p=d[x];
		for(int i=20;~i;i--)
			if(d[f[x][i]]>=p-k)
				x=f[x][i];
		printf("%d ",query(p,rt[dfn[x]+sz[x]-1],rt[dfn[x]-1])-1);
	}
	return 0;
}