树的重链剖分：优化树形结构的高效算法与实现

核心逻辑与数学原理

树的重链剖分（Heavy Path Decomposition）是一种将树形拓扑结构无损转换为线性结构的先进技术。其核心动机在于打破树形分支的离散性，使树上任意两条节点路径或子树区间能够同构映射为最高 $O(\log N)$ 段连续的内存区间，从而利用线段树或树状数组实现 $O(\log N)$ 级的动态维护。

1. 核心定义

对于树中任意非叶子节点 $u$：

重儿子 (Heavy Son)：在其所有子节点 $v \in \text{adj}[u]$ 中，子树规模最大（即 $\text{siz}[v]$ 最大）的节点，记为 $\text{son}[u]$。若有多个子树大小相同的子节点，任选其一。
轻儿子 (Light Son)：除重儿子外的所有其他子节点。
重边 (Heavy Edge)：连接节点 $u$ 与其重儿子 $\text{son}[u]$ 的边。
轻边 (Light Edge)：连接节点 $u$ 与其轻儿子的边。
重链 (Heavy Chain)：由多条重边首尾相连组合而成的极大链。整个树形结构会被严格划分为若干条互不相交的重链。所有叶子节点如果没有重儿子，则自成一条独立重链。

2. 数学定理与复杂度证明

定理：从任意节点 $u$ 向上走向根节点的路径中，经过的轻边数量和重链断开跳转的次数，严格不大于 $\log_2 N$。证明：根据重儿子定义，当从节点 $u$ 沿着一条轻边走向其父节点 $f$ 时，必然满足 $\text{siz}[u] \le \frac{1}{2} \text{siz}[f]$。也就是说，每经过一条轻边，当前所在的子树规模至少翻倍。由于树的总节点数为 $N$，这种翻倍操作最多发生 $\log_2 N$ 次。由此可证，任何树上路径都可以被拆解为最高 $O(\log N)$ 段重链区间。

状态设计与算法推导

实现重链剖分需要两轮独立的 DFS 过程。

1. 第一轮 DFS (预处理拓扑属性)

定义状态数组：

$\text{fa}[u]$：$u$ 的父节点。
$\text{dep}[u]$：$u$ 的拓扑深度。
$\text{siz}[u]$：以 $u$ 为根的子树节点总数。
$\text{son}[u]$：$u$ 的重儿子编号。

状态转移方程：

$$\text{siz}[u] = 1 + \sum_{v \in \text{adj}[u], v \neq \text{fa}[u]} \text{siz}[v]$$

$$\text{son}[u] = \arg\max_{v} \{\text{siz}[v] \mid v \in \text{adj}[u], v \neq \text{fa}[u]\}$$

2. 第二轮 DFS (剖分链并确定线性序列)

定义状态数组：

$\text{top}[u]$：$u$ 所在重链的顶端节点（深度最小的点）。
$\text{dfn}[u]$：$u$ 经过剖分后的新时间戳（即在线性序列中的索引）。

剖分策略：

重儿子优先原则：在向下递归时，必须首先对重儿子 $\text{son}[u]$ 进行深度遍历。这保证了同一条重链上的所有节点在 $\text{dfn}$ 序列中占有一段连续的内存地址。
状态传递：
- 对于重儿子 $\text{son}[u]$，其链顶直接继承：$\text{top}[\text{son}[u]] = \text{top}[u]$。
- 对于任意轻儿子 $v$，其自成新链起点，链顶为其自身：$\text{top}[v] = v$。

C++ 标准源码

#include <iostream>
#include <vector>
#include <algorithm>

const int MAXN = 200005;

std::vector<int> adj[MAXN];
int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN];
int top[MAXN], dfn[MAXN], rnki[MAXN], tim;

// 第一遍 DFS：计算 fa, dep, siz, son
void dfs1(int u, int p) {
    fa[u] = p;
    dep[u] = dep[p] + 1;
    siz[u] = 1;
    son[u] = 0; // 初始化无重儿子

    int max_siz = 0;
    for (size_t i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];
        if (v == p) continue;

        dfs1(v, u);
        siz[u] += siz[v];
        if (siz[v] > max_siz) {
            max_siz = siz[v];
            son[u] = v; // 更新重儿子
        }
    }
}

// 第二遍 DFS：计算 top, dfn，注意重儿子优先
void dfs2(int u, int t) {
    top[u] = t;
    tim++;
    dfn[u] = tim;
    rnki[tim] = u; // 映射反查：线性索引对应的原树节点

    if (!son[u]) return; // 叶子节点断点

    // 致命踩坑点：必须且只能首先对重儿子进行递归，确保重链序列连续
    dfs2(son[u], t);

    for (size_t i = 0; i < adj[u].size(); ++i) {
        int v = adj[u][i];
        if (v == fa[u] || v == son[u]) continue;
        dfs2(v, v); // 轻儿子自成新链，链顶为其自身
    }
}

// 跳重链求 LCA（工业标准，常数极小，吊打倍增）
int lca_by_heavy_edge(int u, int v) {
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) {
            std::swap(u, v);
        }
        u = fa[top[u]]; // 将链顶更深的节点向上跳到其父节点处
    }
    return dep[u] < dep[v] ? u : v;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, root;
    if (!(std::cin >> n >> root)) return 0;

    for (int i = 1; i < n; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dep[0] = 0;
    tim = 0;

    dfs1(root, 0);
    dfs2(root, root);

    // 输出每个点拍平后的线性序列位置
    for (int i = 1; i <= n; ++i) {
        std::cout << "Node " << i << " Map to Segment-Tree Index: " << dfn[i] << "\n";
    }

    return 0;
}

NOIP 实战避坑指南

第二遍 DFS 中混淆重儿子判定条件： 在 dfs2 遍历邻接表时，极易漏掉 if (v == son[u]) continue; 导致对重儿子进行二次深度遍历。这不仅会完全破坏重链的线性物理地址连续性，让后续的线段树区间查询彻底失效，还会因为死循环产生 SIGSEGV。
多组数据未初始化 tim 或 son 数组： son 数组存储的是重儿子指针。如果有多组测试数据，未将 son 数组全部清零，在遇到叶子节点时，其原本没有重儿子，却可能读取到上一组数据的残留脏数据，导致 dfs2 继续向下调用不存在的节点，引发内存非法越界。

经典 NOIP/洛谷真题

1. 洛谷 P2590 [ZJOI2008] 树的统计

题意描述： 给定一棵包含 $N$ 个节点的树，每个节点有其权值。需要实现三种操作：修改某个节点的权值；查询节点 $u$ 到 $v$ 路径上所有节点权值的最大值；查询节点 $u$ 到 $v$ 路径上所有节点权值的总和。
问题本质与核心思路： 树链剖分的标准模板应用。核心思路是通过 dfs1 和 dfs2 将树拍平。因为树剖保证了重链在 $\text{dfn}$ 序列中的连续性，所以查询 $u$ 到 $v$ 的路径时，若 top[u] != top[v]，则让链顶较深的那个节点（假设为 $u$）通过线段树对连续区间 $[\text{dfn}[\text{top}[u]], \text{dfn}[u]]$ 进行最大值或和的查询，然后令 $u = \text{fa}[\text{top}[u]]$ 跳出该链。当两者处于同一条链时，最后对连续区间 $[\min(\text{dfn}[u], \text{dfn}[v]), \max(\text{dfn}[u], \text{dfn}[v])]$ 进行一次线段树操作即可结算。

2. 洛谷 P2146 [NOI2015] 软件包管理器

题意描述： 软件包的依赖关系呈一棵树状结构，卸载或安装某个软件会影响一系列节点。具体而言：安装软件 $x$ 时，需要将其到根节点路径上的所有未安装软件全部安装；卸载软件 $x$ 时，需要将其及其子树内的所有已安装软件全部卸载。求每次操作改变了状态的软件数量。
问题本质与核心思路： 重链剖分对路径和子树的综合映射。安装操作本质是将 $x$ 到根节点的路径上的节点状态全部置为 1（已安装），这需要利用树剖在 $O(\log^2 N)$ 的时间内分解为多个连续线性区间由线段树进行覆盖。卸载操作则是将以 $x$ 为根的整棵子树状态全置为 0，根据重链剖分性质，任意子树在 $\text{dfn}$ 序列中也是一个完全连续的闭区间 $[\text{dfn}[x], \text{dfn}[x] + \text{siz}[x] - 1]$。这使子树卸载操作直接转化为单次线段树区间覆盖，展现了树剖统御路径与子树的双重能力。