如何把这段代码优化到 $O( \log n)$

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
vector<int>root;
int dfn[N],siz[N],dep[N],puck[N],dp[N][21],id;
vector<int>edge[N];
void dfs(int u,int fa)
{
	dp[u][0]=fa;
	for(int i=1;i<=20;++i)
		dp[u][i]=dp[dp[u][i-1]][i-1];
	dep[u]=dep[fa]+1;
	dfn[u]=++id;
	siz[u]=1;
	for(auto &v:edge[u])
	{
		dfs(v,u);
		siz[u]+=siz[v];
	}
}
int calck(int x,int k)
{
	int res=x;
	for(int i=20;i>=0;--i)
	{
		if(k&(1<<i))
			res=dp[res][i];
	}
	return res;
}

//

vector<int>tr[N<<2];
void build(int p,int pl,int pr)
{
	for(int i=pl;i<=pr;++i)
		tr[p].emplace_back(puck[i]);
	sort(tr[p].begin(),tr[p].end());
	if(pl==pr)
		return ;
	int mid=(pl+pr)>>1;
	build(p<<1,pl,mid);
	build(p<<1|1,mid+1,pr);
}
int query(int p,int pl,int pr,int L,int R,int val)
{
	if(R<pl||pr<L)
		return 0;
	if(L<=pl&&pr<=R)
	{
		int x=lower_bound(tr[p].begin(),tr[p].end(),val)-tr[p].begin()-1;
		return x;
	}
	int mid=(pl+pr)>>1;
	return query(p<<1,pl,mid,L,R,val)+query(p<<1|1,mid+1,pr,L,R,val);
}

//
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n,m;
	cin>>n;
	for(int i=1;i<=n;++i)
	{
		int x;
		cin>>x;
		if(x)edge[x].emplace_back(i);
		else root.emplace_back(i);
	}
	for(auto &rt:root)
		dfs(rt,0);
//	dfs(1,0);
	for(int i=1;i<=n;++i)
		puck[dfn[i]]=dep[i];
	build(1,1,n);
	for(cin>>m;m;--m)
	{
		int x,k;
		cin>>x>>k;
		int cy=calck(x,k);
		cout<<
		max(0LL,query(1,1,n,dfn[cy],dfn[cy]+siz[cy]-1,dep[x]+1)-
			query(1,1,n,dfn[cy],dfn[cy]+siz[cy]-1,dep[x])
			-1)
		<<' ';
	}
}