rt.

请说 Luogu 机子可以跑 $10^9$，求 dalao 帮忙卡常：

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define PII pair<int,int>
#define x first
#define y second
#define re register
#define il inline
const int N=1e6+10;
int n,q;
int ne[N<<1],e[N<<1],h[N],idx;
int dfsx[N],dep[N],where[N],siz[N],cnt;
int f[N][25],__2[N];
struct node{
	int l,r,k,id;
}Q[N];
int ANS[N];
int many[N],len,idex;
il void add(int a,int b){
	ne[++idx]=h[a],e[idx]=b,h[a]=idx;
	return ;
}
il void dfs(int now,int fa){
	f[now][0]=fa;
	for(int i=1;i<25;i++)
		f[now][i]=f[f[now][i-1]][i-1];
	dep[now]=dep[fa]+1,dfsx[++cnt]=now,where[now]=cnt,siz[now]=1;
	for(re int i=h[now];i;i=ne[i]){
		int j=e[i];
		if(j==fa) continue;
		dfs(j,now),siz[now]+=siz[j];
	} 
}
il int get_k(int a,int k){ 
	int p=0; 
	while(k){
		if(k&1) a=f[a][p]; 
		p++,k>>=1; 
	} 
	return a; 
}
il bool cmp(node a,node b){
	return ((a.l/len!=b.l/len)?(a.l<b.l):(a.r<b.r));
}
signed main(){
	__2[0]=1;
	for(re int i=1;i<25;++i)
		__2[i]=__2[i-1]*2;
	scanf("%lld%lld",&n,&q);
	for(re int i=2;i<=n;++i){
		int x;scanf("%lld",&x);
		add(x,i),add(i,x);
	}
	dfs(1,0);
	for(re int i=1;i<=q;++i){
		int v,p;scanf("%lld%lld",&v,&p);
		int x=get_k(v,p);
		if(x>=1) Q[++idex]={where[x],where[x]+siz[x]-1,dep[v],i};
	}
	len=sqrt(n),sort(Q+1,Q+idex+1,cmp);
	int l=1,r=0;
	for(re int i=1;i<=idex;++i){
		while(l>Q[i].l) --l,++many[dep[dfsx[l]]];
		while(r<Q[i].r) ++r,++many[dep[dfsx[r]]];
		while(l<Q[i].l) --many[dep[dfsx[l]]],++l;
		while(r>Q[i].r) --many[dep[dfsx[r]]],--r;
		ANS[Q[i].id]=many[Q[i].k]-1;
	}	
	for(re int i=1;i<=q;++i)
		printf("%lld ",ANS[i]);
}