已知 Wa on #10

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll GetLL(){
	ll x = 0,h = 1;
	char ch = getchar();
	while(!(ch=='-'||('0'<=ch&&ch<='9'))) ch = getchar();
	if(ch=='-') h = -1;
	else x = ch-'0';
	ch = getchar();
	while('0'<=ch&&ch<='9'){
		x = x*10+ch-'0';
		ch = getchar();
	}
	return x*h;
}
const ll N = 100010;
ll n,Q;
vector<ll> vec[N];
ll anc[N][40];
ll dep[N];
vector<ll> rt;
ll siz[N],son[N];
void dfs1(ll id,ll fa){
	anc[id][0] = fa;
	siz[id]++;
	ll mx = 0;
	for(ll j = 30; j >= 1; j--) anc[id][j] = anc[anc[id][j-1]][j-1];
	for(auto v : vec[id]){
		if(v==fa) continue;
		dep[v] = dep[id]+1;
		dfs1(v,id);
		if(siz[v]>mx) mx = siz[v],son[id] = v;
		siz[id]+=siz[v];
	}
}
ll req[N],num = 0,ls[N],rs[N];//id's son : (ls[id],rs[id])
void ReDfs(ll id,ll fa){
	num++,req[num] = id;
	ls[id] = num;
	if(son[id]) ReDfs(son[id],id);
	for(auto v : vec[id]){
		if(v==fa||v==son[id]) continue;
		ReDfs(v,id);
	}
	rs[id] = num;
}
ll AskFather(ll id,ll k){
	for(ll j = 30; j >= 0; j--){
		if(k&(1<<j)){
			id = anc[id][j];
			k-=(1<<j);
		}
	}
	return id;
}

//莫队 

ll BelSize;
#define bel(x) (x/BelSize) 
struct question{
    ll id;
    ll ql;
    ll qr;
    ll val;
    bool operator <(const question &b) const{
        return bel(ql)==bel(b.ql)?qr<b.qr:bel(ql)<bel(b.ql);
    }
} q[N];
ll qtot = 0;
ll ans[N];
ll tot[N];
void add(ll id){
	tot[req[id]]++;
}
void del(ll id){
	tot[req[id]]--;
}
void Solve(){
	sort(q+1,q+qtot+1);
	for(ll i = 1,l = 1,r = 0; i <= qtot; i++){
		if(q[i].ql==-1){
			ans[q[i].id] = 0;
			continue;
		}
        while (l > q[i].ql) add(--l);
        while (r < q[i].qr) add(++r);
        while (l < q[i].ql) del(l++);
        while (r > q[i].qr) del(r--);
        ans[q[i].id] = tot[q[i].val]-1;
    }
    for(ll i = 1; i <= qtot; i++) printf("%lld ",ans[i]);
}

//莫队 

int main(){
	n = GetLL();
	BelSize = sqrt(n);
	for(ll i = 1; i <= n; i++){
		ll x = GetLL();
		if(x==0){
			rt.push_back(i);
			continue;
		}
		vec[x].push_back(i);
		vec[i].push_back(x);
	}
	for(auto v : rt){
		dep[v] = 0;
		dfs1(v,0);
		ReDfs(v,0);
		//for(ll i = 1; i <= n; i++) printf("%lld ",req[i]);
	}
	for(ll i = 1; i <= n; i++) req[i] = dep[req[i]];
	//for(ll i = 1; i <= n; i++) printf("%lld ",req[i]);
	Q = GetLL();
	while(Q--){
		ll id = GetLL(),k = GetLL();
		if(k>dep[id]){
			qtot++;
			q[qtot].id = qtot;
			q[qtot].ql = -1;
			q[qtot].qr = 0;
			q[qtot].val = 0;
			continue;
		}
		id = AskFather(id,k);
		//id 的 k 级 son 
		//printf("%lld\n",id);
		//求 req[] 在 (ls[id],rs[id]] 中 dep[id]+k 的个数 
		qtot++;
		q[qtot].id = qtot;
		q[qtot].ql = ls[id]+1;
		q[qtot].qr = rs[id];
		q[qtot].val = dep[id]+k;
	}
	Solve();
	return 0;
}