题意：给出一个森林，求和一个点有相同k级祖先的点有多少

---

倍增求父亲然后和上题一样还不用哈希了...

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;typedef long long ll;#define pii pair
         
          #define MP make_pair #define fir first#define sec secondconst int N=1e5+5;int read(){ char c=getchar();int x=0,f=1; while(c<'0'||c>'9'){if(c=='-')f=-1; c=getchar();} while(c>='0'&&c<='9'){x=x*10+c-'0'; c=getchar();} return x*f;}int n, Q, x, k, root[N];vector
          
            q[N];int ans[N];struct edge{int v, ne;}e[N<<1];int cnt, h[N];inline void ins(int u, int v) { e[++cnt]=(edge){v, h[u]}; h[u]=cnt;}int size[N], mx[N], deep[N], big[N], fa[N][18];void dfs(int u) { for(int i=1; (1<
           
            <=deep[u]; i++) fa[u][i] = fa[fa[u][i-1]][i-1]; size[u]=1; for(int i=h[u];i;i=e[i].ne) { deep[e[i].v] = deep[u]+1; fa[e[i].v][0] = u; dfs(e[i].v); size[u] += size[e[i].v]; if(size[e[i].v] > size[mx[u]]) mx[u] = e[i].v; }}int f[N];void update(int u, int val) { f[deep[u]]+=val; for(int i=h[u];i;i=e[i].ne) if(!big[e[i].v]) update(e[i].v, val);}inline int cal(int d) { return d>n ? 0 : f[d] - 1; }void dfs(int u, int keep) { for(int i=h[u];i;i=e[i].ne) if(e[i].v != mx[u]) dfs(e[i].v, 0); if(mx[u]) dfs(mx[u], 1), big[mx[u]]=1; update(u, 1); for(int i=0; i<(int)q[u].size(); i++) ans[q[u][i].fir] = cal(q[u][i].sec); big[mx[u]]=0; if(!keep) update(u, -1);}int main() { //freopen("in","r",stdin); n=read(); for(int i=1; i<=n; i++) { x=read(); if(x==0) root[++root[0]]=i; else ins(x, i); } for(int i=1; i<=root[0]; i++) dfs(root[i]); Q=read(); for(int i=1; i<=Q; i++) { x=read(); k=read(); int _=deep[x]; for(int j=0; j<17; j++) if((1<