来篇莫队，支持正义根号。
发现是数颜色，这不是我们莫队的经典题目吗，所以考虑莫队。
发现 \(k\) 级儿子挺好，这给出了两个性质，分别在 bfs 序和 dfs 序上。
- bfs 序上，同一子树内深度相同的点相邻。
- dfs 序上，可以把子树问题拍成区间问题。
你就把树拍成 dfs 序再拍成 bfs 序，借助 dfs 序的帮助在子树区间内查询深度为某值的点的 bfs 序的区间，然后你就把这个问题转化为了完全的区间问题。
然后就可以美美的跑莫队了！！！
总复杂度 \(O(n\sqrt m)\)。
话说跑主席树是不是 \(O(m\log n)\) 来着……
code：
// code by 樓影沫瞬_Hz17
#include <bits/stdc++.h>using namespace std;const int N = 2e5 + 10, B = 340;int n, m;int nxt[N * 2], hd[N], to[N * 2], cne;inline void add(int u, int v) { nxt[++ cne] = hd[u], to[cne] = v, hd[u] = cne; }int id_dfs, id_bfs;
int dfn[N], dep[N], sz[N], rdfn[N];
inline void dfs(int u, int f) { // 拍成 dfs 序dfn[u] = ++ id_dfs, sz[u] = 1;rdfn[id_dfs] = u;dep[u] = dep[f] + 1;for(int i = hd[u]; i; i = nxt[i]) {int v = to[i];dfs(v, u);sz[u] += sz[v];}
}int bfn[N];
inline void bfs() { // 拍成 bfs 序queue<int> q; q.push(0);while(!q.empty()) {int u = q.front(); q.pop();bfn[u] = ++ id_bfs;for(int i = hd[u]; i; i = nxt[i]) q.push(to[i]);}
} struct Que {int l, r, id;
} q[N];
int Q, ans[N], pos[N];int a[N], b[N];
int cnt[N], sum;vector<int> st[N];
inline void calc_query() { // 处理询问for(int i = 1; i <= n + 1; i ++) st[dep[rdfn[i]]].push_back(i);for(int i = 1, v, k; i <= m; i ++) {cin >> v >> k;int l1 = dfn[v], r1 = dfn[v] + sz[v] - 1;auto itl = (lower_bound(st[dep[v] + k].begin(), st[dep[v] + k].end(), l1));auto itr = (upper_bound(st[dep[v] + k].begin(), st[dep[v] + k].end(), r1) - 1);if(itl == st[dep[v] + k].end() || itr < st[dep[v] + k].begin() || *itl > *itr) {ans[i] = 0;continue;}int l = *itl, r = *itr;l = rdfn[l];r = rdfn[r];l = bfn[l];r = bfn[r];q[++ Q] = {l, r, i};}for(int i = 1; i <= n; i ++) b[bfn[i]] = a[i];
}map<string, int> mp;
int cntn;int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);cin >> n;int rt = 0;string s;for(int i = 1, f; i <= n; i ++) {cin >> s >> f;add(f, i);if(!mp[s]) mp[s] = ++ cntn;a[i] = mp[s];}dfs(rt, rt);bfs();cin >> m;calc_query();for(int i = 1; i <= n; i ++) pos[i] = (i - 1) / B + 1;sort(q + 1, q + 1 + Q, [pos](Que a, Que b) { return pos[a.l] == pos[b.l] ? pos[a.l] & 1 ? a.r < b.r : a.r > b.r : pos[a.l] < pos[b.l]; });for(int i = 1, l = 1, r = 0; i <= Q; i ++) {while(l < q[i].l) sum -= !-- cnt[b[l ++]];while(l > q[i].l) sum += !cnt[b[-- l]] ++;while(r < q[i].r) sum += !cnt[b[++ r]] ++;while(r > q[i].r) sum -= !-- cnt[b[r --]];ans[q[i].id] = sum;}for(int i = 1; i <= m; i ++) cout << ans[i] << '\n';return 0;
}