CodeForces

Solution

关于树上启发式合并戳这。

这里主要是写几个代码理解吧。

Code

#include <cstdio>
#include <vector>
using namespace std;

const int N = 1e5 + 5;

int n, m, f[N][20], lg[N], siz[N], dep[N], sum[N], son[N], len[N], be[N];
bool vis[N];
vector <int> vec[N], ans[N], q[N];

int read() {
    int x = 0, f = 1; char s;
    while((s = getchar()) < '0' || s > '9') if(s == '-') f = -1;
    while(s >= '0' && s <= '9') {x = (x << 1) + (x << 3) + (s ^ 48); s = getchar();}
    return x * f;
}

void init() {
    for(int i = 1; i <= 18; ++ i)
        for(int j = 1; j <= n; ++ j)
            f[j][i] = f[f[j][i - 1]][i - 1];
    for(int i = 2; i <= n; ++ i) lg[i] = lg[i >> 1] + 1;
}

void dfs(const int u) {
    siz[u] = 1;
    for(int i = 0, sz = vec[u].size(); i < sz; ++ i) {
        int v = vec[u][i];
        dep[v] = dep[u] + 1;
        dfs(v);
        siz[u] += siz[v];
        if(siz[son[u]] < siz[v]) son[u] = v;
    }
}

void cal(const int u, const int k) {
    sum[dep[u]] += k;
    for(int i = 0, sz = vec[u].size(); i < sz; ++ i) {
        int v = vec[u][i];
        if(vis[v]) continue;
        cal(v, k);
    }
}

void solve(const int u, const int fa, const int keep) {
    for(int i = 0, sz = vec[u].size(); i < sz; ++ i) {
        int v = vec[u][i];
        if(v == son[u]) continue;
        solve(v, u, 0);
    }
    if(son[u]) solve(son[u], u, 1), vis[son[u]] = 1;
    cal(u, 1);
    if(son[u]) vis[son[u]] = 0;//只有 u 时才保证是重儿子
    for(int i = 0, sz = q[u].size(); i < sz; ++ i) ans[u].push_back(sum[q[u][i]]);
    if(! keep) cal(u, -1);
}

int main() {
    int x, y, z;
    n = read();
    for(int i = 1; i <= n; ++ i) f[i][0] = read(), vec[f[i][0]].push_back(i);
    init(); dfs(0);//这是森林，可以建一个超级源点 0
    m = read();
    for(int i = 1; i <= m; ++ i) {
        x = read(), y = read();
        if(y >= dep[x]) be[i] = 0;//因为有超级源点的存在，所以正式的 dep 从一开始
        else {
            z = dep[x];
            while(y) x = f[x][lg[y]], y -= (1 << lg[y]);
            q[x].push_back(z); be[i] = x;
        }
    }
    solve(0, -1, 1);
    for(int i = 1; i <= m; ++ i)
        if(be[i]) printf("%d ", ans[be[i]][len[be[i]] ++] - 1);//除去自己
        else printf("0 ");
	return 0;
}