树链剖分

Intro

树链剖分有什么用呢？目前我唯一已知的用途是支持动态修改树以及求 LCA（常数还小点），还有将你的代码量加上 1 kib。

树链剖分将树分成若干链的形式，这样可以维护路径上的信息。也就是将一个树剖分成一堆序列。树链剖分分为重链剖分，长链剖分，实链剖分（用于 LCT 的剖分）。

大多数情况下，树链剖分一般指重链剖分。

重链剖分将树上任意一条路径划分成不超过 $\log(n)$ 条连续的链，都是自底向上的链，还能保证 DFS 序连续，这样可以用一些维护序列的东西来维护路径上的信息（such as 线段树）。

（线段树就不短了，再加一个树剖，我感觉不熟练的话就可以提前在聊天框里发 gg 了这样还能加 5 rp 值）。

不过写完后发现树剖也不是很长，主要长度感觉是线段树贡献的。

实现

给一些定义：

1. 重子节点：表示其子节点中子树最大的节点，有多个的话取其一。
2. 轻子节点：表示其子节点中除了重子节点以外的所有节点。
3. 重边：从一个节点到重子节点的边为重边。
4. 轻边：到轻子节点的边。
5. 重链：若干条首尾衔接的重边构成的，落单的节点也当作重链。

树剖的实现分为两个 DFS 的过程，第一遍求出每个节点的父亲，节点的深度，节点子树的个数，重儿子，第二遍求出节点所在重链的顶部节点，DFS 序，和 DFS 序所对应的节点编号。

Code：

void dfs1(int u) {
    son[u] = -1; // 一开始不确定重儿子是谁
    siz[u] = 1; // 子树大小至少为 1，因为本身也算在字数里
    for(int i = lk[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(!dep[v]) { // 如果没遍历过这个节点
            dep[v] = dep[u] + 1; // 深度
            fa[v] = u; // 记录父亲
            dfs1(v);
            siz[u] += siz[v]; // 统计子树大小
            if(son[u] == -1 || siz[v] > siz[son[u]]) // 更新重儿子
                son[u] = v;
        }
    }
}

void dfs2(int u, int t) { // t 指当前重链的顶部节点
    top[u] = t; // 记录节点
    ++cnt;
    dfn[u] = cnt; // DFS 序
    rk[cnt] = u; // 记录 DFS 序对应的节点
    if(son[u] == -1) return ; // 叶子节点就返回
    dfs2(son[u], t); // 优先遍历重儿子，保证同一条链上的 DFS 序连续
    for(int i = lk[u]; i; i = e[i].nxt) {
        int v = e[i].v;
        if(v != son[u] && v != fa[u]) // 走到了一个轻边，当然换了一条链
            dfs2(v, v); // 所以链的顶部节点就更换成了它自己
    }
}

你会发现每次向下走一条轻边，所在子树大小就至少除以 2。

怎么用树剖求 LCA 呢？

不断向上跳重链，跳到同一条重链上时，深度较小的节点便是 LCA。

int lca(int u, int v) {
    while(top[u] != top[v]) {
        if(dep[top[u]] > dep[top[v]]) u = fa[top[u]];
        else v = fa[top[v]];
    }

    return dep[u] > dep[v] ? v : u;
}