线段树合并
考虑把询问离线，转化题意，也就是求 \(v\) 的 \(p\) 级祖先有多少个 \(p\) 级儿子，那么询问的答案就是 「\(p\) 级祖先有多少个 \(p\) 级儿子数量 - 1」（减去自己）。\(p\) 级祖先可以倍增找到。
我们可以维护根节点的 \(k\) 级儿子。因为在遍历的过程中，子节点到根节点的深度是不变的。考虑如何合并子节点的信息，其实只需要简单的线段树合并即可。
考虑答案，显然 \(v\) 的 \(p\) 级儿子就是根节点的 \(p+now\) 级儿子，\(now\) 表示 \(v\) 的深度。
复杂度 \(O(n\log n)\)。
#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const int N = 1e5 + 10;
int n, m, cnt;
int h[N];
struct node {
int to, nxt;
} e[N << 1];
void add(int u, int v) {
e[++cnt].to = v;
e[cnt].nxt = h[u];
h[u] = cnt;
}
int anc[N][20], dep[N];
std::vector<pii> ve[N];
int depth, now;
void dfs(int u, int fa) {
anc[u][0] = fa;
dep[u] = dep[fa] + 1;
depth = std::max(depth, dep[u]);
for(int i = 1; i < 19; i++) {
anc[u][i] = anc[anc[u][i - 1]][i - 1];
}
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa) continue;
dfs(v, u);
}
}
int find(int x, int y) {
for(int i = 18; i >= 0; i--) {
if(y >= (1 << i)) y -= (1 << i), x = anc[x][i];
}
return x;
}
int tot;
int ans[N];
struct seg {
int ls, rs, v;
} t[N * 40];
void ins(int &u, int l, int r, int x) {
if(!u) u = ++tot;
if(l == r) {
t[u].v++;
return;
}
int mid = (l + r) >> 1;
if(x <= mid) ins(t[u].ls, l, mid, x);
else ins(t[u].rs, mid + 1, r, x);
}
void mg(int p1, int p2, int l, int r) {
if(l == r) {
t[p1].v += t[p2].v;
return;
}
int mid = (l + r) >> 1;
if(t[p1].ls && t[p2].ls) mg(t[p1].ls, t[p2].ls, l, mid);
else if(t[p2].ls) t[p1].ls = t[p2].ls;
if(t[p1].rs && t[p2].rs) mg(t[p1].rs, t[p2].rs, mid + 1, r);
else if(t[p2].rs) t[p1].rs = t[p2].rs;
}
int query(int u, int l, int r, int x) {
if(l == r) {return t[u].v;}
int mid = (l + r) >> 1;
if(x <= mid) return query(t[u].ls, l, mid, x);
return query(t[u].rs, mid + 1, r, x);
}
void dfs2(int u, int fa) {
now++;
for(int i = h[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(v == fa) continue;
dfs2(v, u);
mg(u, v, 1, depth);
}
ins(u, 1, depth, now);
for(auto x : ve[u]) {
ans[x.fi] = query(u, 1, depth, now + x.se) - 1;
}
now--;
}
std::vector<int> rt;
void Solve() {
std::cin >> n;
tot = n;
for(int i = 1; i <= n; i++) {
int x;
std::cin >> x;
if(!x) rt.push_back(i);
else add(x, i), add(i, x);
}
for(auto x : rt) dfs(x, 0);
std::cin >> m;
for(int i = 1; i <= m; i++) {
int x, y;
std::cin >> x >> y;
int rt = find(x, y);
ve[rt].push_back({i, y});
}
for(auto x : rt) dfs2(x, 0);
for(int i = 1; i <= m; i++) std::cout << ans[i] << " \n"[i == m];
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
Solve();
return 0;
}