可以发现，统计同k级祖先数，可以看成统计k级祖先k级儿子有几个。
那么，就可以dsu on tree来统计了。
依据上面的思路，我们就可以把询问挂到k级祖先上，把询问变成统计以该祖先为根的深度为k的孩子数为多少。
那么，首选就是找这个k级祖先，因为暴力找肯定会T，所以我们可以倍增跳。
然后挂上询问，需要注意的是，这里是森林图，需要for循环遍历图。
那么，我们可以dsu on tree来统计深度。
首先，因为dsu on tree很难保证和某个节点的关联性，所以要以某个点为根去统计深度，这样会难以实现。
那么换一下思路。
对于当前u，我们统计出它子节点的所有深度。
那么相当于u深度为1的子节点数就是d[dep[u]+1]。
那么就可以统计了。注意这里统计的时候原来的那个点不算，所以要减1
// Author: levil #include<bits/stdc++.h> using namespace std; typedef long long LL; typedef pair<LL,int> pii; const int N = 1e5+5; const int M = 1e5+5; const LL Mod = 199999; #define rg register #define pi acos(-1) #define INF 1e9 #define CT0 cin.tie(0),cout.tie(0) #define IO ios::sync_with_stdio(false) #define dbg(ax) cout << "now this num is " << ax << endl; namespace FASTIO{ inline LL read(){ LL x = 0,f = 1;char c = getchar(); while(c < ‘0‘ || c > ‘9‘){if(c == ‘-‘) f = -1;c = getchar();} while(c >= ‘0‘ && c <= ‘9‘){x = (x<<1)+(x<<3)+(c^48);c = getchar();} return x*f; } void print(int x){ if(x < 0){x = -x;putchar(‘-‘);} if(x > 9) print(x/10); putchar(x%10+‘0‘); } } using namespace FASTIO; void FRE(){/*freopen("data1.in","r",stdin); freopen("data1.out","w",stdout);*/} int n,f[N][20],lg[N],dep[N],ans[N],vis[N],ssize[N],son[N],Son,d[N]; struct Query{int id,d;}; vector<int> G[N]; vector<Query> vec[N]; void init() { for(rg int i = 1;i < N;++i) lg[i] = lg[i-1] + ((1<<lg[i-1]) == i); } void dfs(int u,int fa) { dep[u] = dep[fa]+1; f[u][0] = fa,ssize[u] = 1; for(rg int i = 1;i <= lg[dep[u]];++i) f[u][i] = f[f[u][i-1]][i-1]; for(auto v : G[u]) { dfs(v,u); ssize[u] += ssize[v]; if(ssize[v] > ssize[son[u]]) son[u] = v; } } int Get_kfa(int x,int k) { if(k >= dep[x]) return 0; for(rg int i = lg[dep[x]];i >= 0;--i) { if((1<<i) <= k) x = f[x][i],k -= (1<<i); } return x; } void slove(int u,int val) { d[dep[u]] += val; for(auto v : G[u]) { if(v == Son) continue; slove(v,val); } } void dfs1(int u,int opt) { vis[u] = 1; for(auto v : G[u]) { if(v == son[u]) continue; dfs1(v,0); } if(son[u]) dfs1(son[u],1),Son = son[u]; slove(u,1); Son = 0; for(auto t : vec[u]) ans[t.id] = d[t.d+dep[u]]-1; if(opt == 0) slove(u,-1); } int main() { init(); n = read(); for(rg int i = 1;i <= n;++i) { int x;x = read(); if(x == 0) continue; G[x].push_back(i); } for(rg int i = 1;i <= n;++i) if(dep[i] == 0) dfs(i,0); int m;m = read(); for(rg int i = 1;i <= m;++i) { int v,p;v = read(),p = read(); int ff = Get_kfa(v,p); if(ff == 0) ans[i] = 0; else vec[ff].push_back(Query{i,p}); } for(rg int i = 1;i <= n;++i) if(!vis[i]) dfs1(i,0); for(rg int i = 1;i <= m;++i) printf("%d%c",ans[i],i == m ? ‘\n‘ : ‘ ‘); system("pause"); } /* 6 0 1 1 2 2 3 5 5 1 5 2 5 3 5 4 5 5 */
原文：https://www.cnblogs.com/zwjzwj/p/13611815.html
