原题链接
解析
首先，求完 \(k\) 级祖先后，问题转化为求一个结点子树内指定深度的结点个数。一个很朴素的想法是，每个结点上维护一个数组 \(cnt\)，\(cnt_i\) 表示子树内深度为 \(i\) 的结点个数，把子树信息简单合并一下就可以得到答案。为了优化合并效率与空间，可以使用动态开点线段树来进行线段树合并。
时间复杂度 \(O(n\log n)\)，空间复杂度 \(O(n\log n)\)。
然而，256MiB 的空间限制并不允许额外贡献三个 \(O(n\log n)\) 大小数组的线段树合并通过。
让我们来看一个在线做法。先求 DFS 序，将树拍平成序列。我们知道子树内结点在 DFS 序中对应着一段连续的区间：\([dfn_x,dfn_x + siz_x - 1]\)，其中 \(dfn_x\) 表示点 \(x\) 的 DFS 序，\(siz_x\) 表示以 \(x\) 为根子树大小。所以原问题相当于求区间内指定数的个数，可以离线后用树状数组解决，在这里不多赘述。对于在线做法，考虑将所有结点按照深度分类，并按照 DFS 序排序，这样查询时只需在对应数列 \(a\) 中二分左右端点 \(l,r\) 使得 \(l\) 是满足 \(a_l>dfn_x\) 的最小 \(l\)，\(r\) 是满足 \(a_r \le dfn_x + siz_x - 1\) 的最大 \(r\)。
时间复杂度 \(O(m\log n)\)，空间复杂度 \(O(n\log n)\)（如果用了倍增求 \(k\) 级祖先）。
代码
注意题目要求统计时不包含 \(u\)。
#include <bits/stdc++.h>
#define ls(x) ((x) << 1)
#define rs(x) ((x) << 1 | 1)
#define mid (l + r >> 1)
using namespace std;
const int N = 1e6 + 5,M = 20;
typedef long long ll;
typedef pair<int,int> pii;
int dep[N],fa[N][M],siz[N],dfn[N];
vector<int> t[N],p[N];
int cnt;
void dfs(int x){dfn[x] = ++cnt;dep[x] = dep[fa[x][0]] + 1;siz[x] = 1;p[dep[x]].push_back(dfn[x]);for(int i=1;i<M;i++){fa[x][i] = fa[fa[x][i - 1]][i - 1];}for(int nx : t[x])if(nx != fa[x][0]){dfs(nx);siz[x] += siz[nx];}
}
int get(int a,int b){for(int i=M - 1;i>=0;i--){if(b & (1 << i)){a = fa[a][i];}}return a;
}
int sol(int x,int k){if(!x) return 0;int a = lower_bound(p[k].begin(),p[k].end(),dfn[x]) - p[k].begin();int b = upper_bound(p[k].begin(),p[k].end(),dfn[x] + siz[x] - 1) - p[k].begin();return b - a - 1;
}
int main(){ios::sync_with_stdio(false);cin.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);int n,q;cin>>n>>q;for(int i=2;i<=n;i++){cin>>fa[i][0]; t[fa[i][0]].push_back(i);t[i].push_back(fa[i][0]);}dfs(1);for(int i=1;i<=q;i++){int u,k;cin>>u>>k;cout<<sol(get(u,k),dep[u])<<" ";}return 0;
}