树链剖分

简介

或许叫轻重链剖分更好一点？

int dep[maxn], son[maxn], sz[maxn], f[maxn]; 
void dfs(int u, int fa) {
    int Max = 0; sz[u] = 1;
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa) continue;
        f[v] = u; dep[v] = dep[u] + 1;
        dfs(v, u); sz[u] += sz[v];
        if (sz[v] > Max) Max = sz[v], son[u] = v;
    }
}

int top[maxn], id[maxn], c2, bl[maxn];
void dfs(int u, int fa, int topf) {
    top[u] = topf; id[u] = ++c2; bl[c2] = u;
    if (son[u]) dfs(son[u], u, topf); 
    for (int i = head[u]; ~i; i = e[i].next) {
        int v = e[i].to; if (v == fa || v == son[u]) continue;
        dfs(v, u, v);
    }
}