算法
(DFS、二分) $O(n\log n)$
记录一下 dfs
每个点的进出时间 $in_v$ 和 $out_v$,然后在同一深度 $d$ 的所有 $in_v$ 中,对 $out_u$ 和 $in_u$ 进行二分查找,其二者下标的差值即为答案。
其中蓝色编号表示进入该点的时间,绿色编号为离开该点的时间。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
const int N = 200005;
vector<int> to[N];
int dep[N];
int in[N];
int out[N];
int k;
vector<int> ls[N];
void dfs(int v, int d) {
in[v] = k++;
dep[v] = d;
for (int u : to[v]) dfs(u, d + 1);
out[v] = k;
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
cin >> n;
rep(i, n - 1) {
int p;
cin >> p;
to[p - 1].push_back(i + 1);
}
dfs(0, 0);
rep(i, n) ls[dep[i]].push_back(in[i]);
rep(i, n) sort(ls[i].begin(), ls[i].end());
int q;
cin >> q;
auto f = [&](int d, int r) {
return lower_bound(ls[d].begin(), ls[d].end(), r) - ls[d].begin();
};
rep(qi, q) {
int u, d;
cin >> u >> d;
--u;
int ans = f(d, out[u]) - f(d, in[u]);
cout << ans << '\n';
}
return 0;
}