链接

Description

给定一棵树， 个查询，每次查询给出 ，查询 子树里深度为 的节点个数。

Solution

题目特征：1.可离线。2.无修改。
显然思路：
把查询离线，思考能否把问题转化成找在树上遍历找每个节点下面所有深度的点并统计。
显然可以用树上启发式合并 实现以上任务，那么只要看我们所查询的深度有多少个节点，加入到答案就可以了。
注意树上启发式合并的思想：
1.暴力找轻链，统计答案，消除贡献。
2.暴力找重链，统计答案，不消除贡献。
3.暴力找轻链，统计答案，不消除贡献，并与重链合并。
如此重链只会计算一次，而树上只有 条轻链，复杂度 得证。

Code

#include <bits/stdc++.h>

const int mod1 = 998244353, mod2 = 1e9 + 9;
const int N = 5e5 + 5;

std::vector<int> G[N];
std::vector<std::pair<int, int> > Query[N];
int sz[N], son[N], n;
long long cnt[N], col[N], ans[N], dep[N], Mx, sum, Son;
void dfs1(int u, int par) { // 轻重链剖分
    sz[u] = 1;
    for (auto &it : G[u]) {
        if (it == par) continue;
        dep[it] = dep[u] + 1;
        dfs1(it, u);
        sz[u] += sz[it];
        if (sz[it] > sz[son[u]]) {
            son[u] = it;
        }
    }
}
void add(int u, int par, int val) {
    cnt[dep[u]] += val; // 深度出现次数增加
    for (auto &it : G[u]) {
        if (it == par || it == Son) continue; // 重儿子不统计 
        add(it, u, val);
    }
}
void dfs2(int u, int par, int opt) {
    for (auto &it : G[u]) {
        if (it == par) continue;
        if (it != son[u]) { // 轻链暴力
            dfs2(it, u, 0);
        }
    }
    if (son[u]) { // 最后处理当前子树的重链
        dfs2(son[u], u, 1); Son = son[u];
    }
    add(u, par, 1); Son = 0; // 递归计算轻链，不清空
    for (auto &it : Query[u]) { 
        ans[it.second] += cnt[it.first];
    }    
    if (!opt) {
        add(u, par, -1), sum = 0, Mx = 0; // 清空
    }
}
void solve() {
    std::cin >> n;
    for (int i = 2; i <= n; i++) {
        int x; std::cin >> x;
        G[i].emplace_back(x);
        G[x].emplace_back(i);
    }    
    int q; std::cin >> q;
    for (int i = 1; i <= q; i++) {
        int u, d; std::cin >> u >> d;
        Query[u].emplace_back(d, i); 
    }
    dfs1(1, 0);
    dfs2(1, 0, 0);
    for (int i = 1; i <= q; i++) {
        std::cout << ans[i] << "\n";
    }
}

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  int T = 1; //std::cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}