麻了，已经尽力卡常了QwQ

我知道有比树剖更好的做法，但是我主要是来练习轻重链剖分和树上启发式合并的QwQ，所以不用在评论区提出更优的做法了噢

反正你提出来了我也照样码树剖

自己估的时间复杂度是$O(Mlog_2N+N log_2N)$

其中树上启发式合并用了$O(Nlog_2N)$

处理$m$次询问的k级祖先用了$O(Mlog_2N)$

如果我做法假了/时间估的不对，请在评论区随便骂我是个弱智并记得指出我的错误，请不要只发个。。。就不理我了捏QwQ

$Talk$ $is$ $cheap,$ $show$ $you$ $the$ $code$ $QwQ$

#include<bits/stdc++.h>
#define ll long long
#define v to[i]
using namespace std;
const ll M=100005;
ll n,m,cnt,pos,ans[M],e[M<<1],to[M<<1],fir[M],fa[M],son[M],sz[M],de[M],note[M],top[M],p[M],fp[M];
struct node{
    short bh;
    ll num;
};
inline ll re(){
    char a=getchar();
    ll ju=1,n=0;
    while(a>'9'||a<'0'){
        if(a=='-') ju=-1;
        a=getchar();
    }
    while(a<='9'&&a>='0') n=(n<<1)+(n<<3)+a-'0',a=getchar();
    return n*ju;
}
inline void pr(ll a){
    if(a<0)
        putchar('-'),pr(a*-1);
    if(a>9)
        pr(a/10),putchar(a%10+'0');
    else
        putchar(a+'0');
}
vector<node>ask[M];
void add(ll,ll),change(ll,ll),dfs1(ll),dfs2(ll,ll),dfs(ll);
ll f(ll,ll);
int main(){
    n=re();
    for(int i=1;i<=n;i++){
        fa[i]=re();
        add(i,fa[i]);
    }
    for(int i=1;i<=n;i++){
        if(fa[i]==0)
            de[i]=1,dfs1(i);
    }
    for(int i=1;i<=n;i++){
        if(fa[i]==0)
            dfs2(i,i);
    }
    m=re();
    for(int i=1;i<=m;i++){
        ll a,b,as;
        a=re(),b=re();
        if(de[a]<=b)
            continue;
        node aa; as=f(a,b);
        aa.bh=i,aa.num=b;
        ask[as].push_back(aa);
    }
    for(int i=1;i<=n;i++){
        if(fa[i]==0)
            dfs(i),change(i,-1);
    }
    for(int i=1;i<=m;i++)
        pr(ans[i]),putchar(' ');
    return 0;
}
void add(ll a,ll b){
    e[++cnt]=fir[a],to[cnt]=b,fir[a]=cnt;
    e[++cnt]=fir[b],to[cnt]=a,fir[b]=cnt;
}
void dfs1(ll no){
    ++sz[no];
    ll maxx=0;
    for(int i=fir[no];i;i=e[i]){
        if(v!=fa[no]){
            de[v]=de[no]+1;
            dfs1(v);
            sz[no]+=sz[v];
            if(sz[v]>maxx)
                maxx=sz[v],son[no]=v;
        }
    }
}
void dfs2(ll no,ll t){
    top[no]=t,p[no]=++pos,fp[pos]=no;
    if(!son[no])
        return;
    dfs2(son[no],t);
    for(int i=fir[no];i;i=e[i]){
        if(v!=fa[no]&&v!=son[no])
            dfs2(v,v);
    }
}
void dfs(ll no){
    for(int i=fir[no];i;i=e[i]){
        if(v!=fa[no]&&v!=son[no])
            dfs(v),change(v,-1);
    }
    if(son[no])
        dfs(son[no]);
    ++note[de[no]];
    for(int i=fir[no];i;i=e[i]){
        if(v!=fa[no]&&v!=son[no])
            change(v,1);
    }
    ll a1=ask[no].size();
    for(int i=0;i<a1;i++)
        ans[ask[no][i].bh]=note[ask[no][i].num+de[no]]-1;
}
void change(ll no,ll k){
    note[de[no]]+=k;
    for(int i=fir[no];i;i=e[i]){
        if(v!=fa[no])
            change(v,k);
    }
}
ll f(ll no,ll k) {
    int d = de[no] - k;
    while (de[top[no]] > d) no = fa[top[no]];
    d = de[no] - d;
    return fp[p[no] - d];
}