第 5.12 章：树链剖分与树上启发式合并

5.12.0 从一道题出发：奶牛快递路上的最贵包裹

先看一道 USACO 风格的题：

🐄 题目：树上路径查询 Farmer John 的农场有 N 个牧场（N ≤ 3×10⁴），由 N-1 条道路连接成一棵树。每个牧场上有一个包裹，价值为 val[i]。 接下来有 Q 次操作（Q ≤ 2×10⁵）：

• Q u v：快递员从牧场 u 走到牧场 v（沿树上唯一路径），询问路径上所有包裹的价值之和；
• U x w：牧场 x 的包裹价值改为 w。

先试试你会的方法

思路 1：LCA 暴力。 用第 5.13 章的倍增 LCA 找到 lca(u,v)，然后沿着 u → lca → v 一步步累加。每次询问最坏走 O(N) 条边。N·Q = 3×10⁴ × 2×10⁵ = 6×10⁹ 次操作——直接超时。

思路 2：欧拉序 + BIT？ 第 5.13 章教过：欧拉序能把子树变成连续区间。但这里问的是路径，路径在欧拉序上不是连续区间，这条路走不通。

思路 3：树上差分？ 差分适合"一次性修改、最后统一查询"，处理不了边修改边查询。

关键观察： 数组上"边修改边查询"的答案是线段树（第 5.7 章）。如果能把树上任意路径变成数组上的连续区间，问题就解决了。

这就是树链剖分（重链剖分，Heavy-Light Decomposition，HLD）要做的事：把树「拍平」成序列，且保证每条路径只由 O(log N) 段连续区间拼成。

拆解这一章需要回答的问题

1. "删除哪个节点使树最平衡"——树的重心（本章热身，也是后续点分治的前置）
2. 怎么把树剖成链？→ 5.12.2：重儿子、重边、重链，两次 DFS
3. 剖完之后路径查询怎么做？→ 5.12.3：跳链 + 线段树完整代码
4. 如果只统计子树信息、不需要修改呢？→ 5.12.4：树上启发式合并（dsu on tree）
5. 三种树上工具怎么选？→ 5.12.5：对比表

学习目标：

• 理解重链剖分的定义与两条关键性质
• 实现两次 DFS（dfs1 求 size/son，dfs2 求 dfn/top）与跳链查询
• 用 HLD + 线段树解决路径修改/查询问题
• 理解 dsu on tree 的 solve(u, keep) 模式与 O(N log N) 复杂度来源

5.12.1 热身：树的重心

在看"剖分"之前，先解决一个更简单但思想相通的问题——它也是理解"子树大小"重要性的热身。

定义

在树中删除某个节点 u，树会分裂成若干棵子树。设 weight(u) = 分裂后最大子树的节点数。使 weight(u) 最小的节点称为树的重心（centroid）。

        1                删除 1：子树 {2,4,5} 和 {3,6,7}，最大 3  ← 重心
      /   \              删除 3：子树 {6,7} 和 {1,2,4,5}，最大 4
     2     3             删除 6：子树 {7} 和其余 5 个点，最大 5
    / \     \
   4   5     6
              \
               7

关键性质

1. 以重心为根时，所有子树的大小都 ≤ N/2。
2. 重心至多有两个，且若有两个，它们相邻。
3. 树中所有点到重心的距离和最小（医院选址类问题的答案）。

一次 DFS 求重心

对每个节点 u，「删除 u 后的最大子树」= max(所有向下子树的 size, N − sz[u])。后者是"向上"的那部分。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN];
int n;
int sz[MAXN], weight[MAXN];   // weight[u] = 删除 u 后最大子树大小

void getCentroid(int u, int fa) {
    sz[u] = 1;
    weight[u] = 0;
    for (int v : adj[u]) {
        if (v == fa) continue;
        getCentroid(v, u);
        sz[u] += sz[v];
        weight[u] = max(weight[u], sz[v]);      // 向下的子树
    }
    weight[u] = max(weight[u], n - sz[u]);      // 向上的子树
}

int main() {
    // 7 节点测试树（同上图）：
    n = 7;
    int us[] = {1,1,2,2,3,6}, vs[] = {2,3,4,5,6,7};
    for (int i = 0; i < 6; i++) { adj[us[i]].push_back(vs[i]); adj[vs[i]].push_back(us[i]); }
    getCentroid(1, 0);
    int best = -1;
    for (int u = 1; u <= n; u++) {
        printf("删除 %d：最大子树 = %d\n", u, weight[u]);
        if (best == -1 || weight[u] < weight[best]) best = u;
    }
    printf("重心 = %d\n", best);
    return 0;
}

运行输出（可自行验证）：

删除 1：最大子树 = 3
删除 2：最大子树 = 4
删除 3：最大子树 = 4
删除 4：最大子树 = 6
删除 5：最大子树 = 6
删除 6：最大子树 = 5
删除 7：最大子树 = 6
重心 = 1

💡 为什么在树链剖分这一章讲重心？ 重心告诉我们：树可以被"比较均匀"地切开。重链剖分用的是同一个思想——按子树大小分轻重。另外，重心是 Platinum 级别点分治的核心前置知识，现在掌握一次 DFS 求法，将来直接受益。

5.12.2 重链剖分：把树剖成 O(log N) 条链

定义

对每个节点 u（以 1 为根）：

• 重儿子（heavy child）：子树最大的儿子。并列时任取一个。叶节点没有重儿子。
• 轻儿子（light child）：其余儿子。
• u 连向重儿子的边叫重边，连向轻儿子的边叫轻边。
• 若干条首尾相接的重边构成一条重链。落单的节点自己也算一条重链。

        1●━━━━3●        ━━━ 重边
       ╱       │╲        ───╯ 轻边
      2●       │ 6●      重链：1-3（顶=1）
     ╱ ╲       │  │╲           1-2（顶=1，2 是 1 的轻儿子开新链）
    ●   ●      ●  ● ●         3-6（顶=3）
    4   5      5  7 8         ...

两条关键性质

性质 1（每条链 DFS 序连续）： 若 DFS 时优先访问重儿子，则每条重链上节点的 DFS 序连续；同时任意子树的 DFS 序也连续。

性质 2（路径 = O(log N) 条链段）： 沿一条轻边从父走到子，子树大小至少减半——若不减半，它就该是重儿子了。因此从任意节点到根最多经过 O(log N) 条轻边，即任意路径最多被拆成 O(log N) 条重链段，而每段都是 DFS 序上的连续区间。

💡 这就是开篇题的答案：路径查询 → O(log N) 段连续区间 → 每段用线段树查一次 → 单次询问 O(log² N)。

两次 DFS 实现

第一次 DFS 求 fa、dep、sz、son（与第 6.8 章求子树大小的树形 DP 相同）：

int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN];

void dfs1(int u, int parent) {
    fa[u] = parent;
    dep[u] = dep[parent] + 1;
    sz[u] = 1;
    son[u] = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;   // 记录重儿子
    }
}

第二次 DFS 求 top（所在重链的链顶）、dfn（DFS 序，即线段树里的位置）、rnk（DFS 序对应的节点）：

int top[MAXN], dfn[MAXN], rnk[MAXN], timer_ = 0;

void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++timer_;
    rnk[timer_] = u;
    if (son[u] == 0) return;
    dfs2(son[u], t);                 // ★ 重儿子优先，继承链顶
    for (int v : adj[u]) {
        if (v != fa[u] && v != son[u]) dfs2(v, v);  // 轻儿子开新链
    }
}

⚠️ dfs2 中 dfs2(son[u], t) 必须先于轻儿子调用——"重儿子优先"正是性质 1 的来源。调换顺序后链上 DFS 序不再连续，整棵树剖分失效。

5.12.3 HLD + 线段树完整实战

跳链：路径查询的核心

查询 u → v 路径时，模仿倍增 LCA的"先跳到同一高度"思想，但一次跳一整条链：

1. 若 top[u] != top[v]（不同链），把链顶更深的那个往上跳：查询 [dfn[top[u]], dfn[u]] 这段区间，然后 u = fa[top[u]]。
2. 跳到同一条链后，u、v 中深度小的就是 LCA，查询 [dfn[u], dfn[v]] 一次即可。

long long pathSum(int u, int v) {
    long long res = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);   // ★ 让 u 的链顶更深
        res += query(1, 1, n, dfn[top[u]], dfn[u]);  // 查询整段链
        u = fa[top[u]];                              // 跳到上一条链
    }
    if (dep[u] > dep[v]) swap(u, v);                 // 现在 dep[u] 小 = LCA
    res += query(1, 1, n, dfn[u], dfn[v]);
    return res;
}

while 循环最多执行 O(log N) 次（每跳一次必经过一条轻边），每次线段树查询 O(log N)，故单次询问 O(log² N)。把 query 换成 update，就是路径修改——代码框架完全一致。

完整可编译程序（路径求和 + 单点修改）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100005;
vector<int> adj[MAXN];
int n, Q;
long long val[MAXN];

// ── 重链剖分数组 ──────────────────────────────
int fa[MAXN], dep[MAXN], sz[MAXN], son[MAXN];
int top[MAXN], dfn[MAXN], rnk[MAXN], timer_ = 0;

// ── 线段树（单点修改 + 区间求和），见第 5.7 章 ──
long long tree_[MAXN * 4];

void build(int node, int l, int r) {
    if (l == r) { tree_[node] = val[rnk[l]]; return; }
    int mid = (l + r) / 2;
    build(node*2, l, mid);
    build(node*2+1, mid+1, r);
    tree_[node] = tree_[node*2] + tree_[node*2+1];
}

void update(int node, int l, int r, int pos, long long v) {
    if (l == r) { tree_[node] = v; return; }
    int mid = (l + r) / 2;
    if (pos <= mid) update(node*2, l, mid, pos, v);
    else update(node*2+1, mid+1, r, pos, v);
    tree_[node] = tree_[node*2] + tree_[node*2+1];
}

long long query(int node, int l, int r, int ql, int qr) {
    if (qr < l || r < ql) return 0;
    if (ql <= l && r <= qr) return tree_[node];
    int mid = (l + r) / 2;
    return query(node*2, l, mid, ql, qr) + query(node*2+1, mid+1, r, ql, qr);
}

// ── 两次 DFS ───────────────────────────────────
void dfs1(int u, int parent) {
    fa[u] = parent;
    dep[u] = dep[parent] + 1;
    sz[u] = 1;
    son[u] = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int t) {
    top[u] = t;
    dfn[u] = ++timer_;
    rnk[timer_] = u;
    if (son[u] == 0) return;
    dfs2(son[u], t);
    for (int v : adj[u]) {
        if (v != fa[u] && v != son[u]) dfs2(v, v);
    }
}

// ── 路径求和：跳链 ──────────────────────────────
long long pathSum(int u, int v) {
    long long res = 0;
    while (top[u] != top[v]) {
        if (dep[top[u]] < dep[top[v]]) swap(u, v);
        res += query(1, 1, n, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (dep[u] > dep[v]) swap(u, v);
    res += query(1, 1, n, dfn[u], dfn[v]);
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> Q;
    for (int i = 1; i <= n; i++) cin >> val[i];
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs1(1, 0);
    dfs2(1, 1);
    build(1, 1, n);          // ★ 按 dfn 序建树，用 rnk 取回原权值

    while (Q--) {
        string op;
        int u, v;
        cin >> op >> u >> v;
        if (op == "Q") {
            cout << pathSum(u, v) << "\n";
        } else {  // "U"：把点 u 的值改成 v
            val[u] = v;
            update(1, 1, n, dfn[u], v);   // ★ 位置是 dfn[u]，不是 u
        }
    }
    return 0;
}

手算验证

用 7 节点的树（节点旁是权值）：

        1(1)
      /      \
    2(10)    3(100)
    /   \       \
 4(1000) 5(10000) 6(5)
                   \
                   7(6)

输入与期望输出：

输入：                          输出：
7 4
1 10 100 1000 10000 5 6
1 2
1 3
2 4
2 5
3 6
6 7
Q 4 7                          1122      （1000+10+1+100+5+6）
Q 5 5                          10000
U 1 999
Q 4 7                          2120      （1000+10+999+100+5+6）

逐个核对：路径 4→7 是 4-2-1-3-6-7，和为 1000+10+1+100+5+6 = 1122；修改节点 1 为 999 后和为 2120。实际运行结果与手算完全一致。

HLD 顺带能做的事

• 求 LCA： 跳到同一条链后深度小的节点就是 LCA——比倍增 LCA 常数更小，且不需要 O(N log N) 的 up 数组。
• 子树修改/查询： 任意子树的 DFS 序是连续区间 [dfn[u], dfn[u]+sz[u]-1]，一次线段树区间操作即可——这正是第 5.13 章欧拉序 + BIT 的能力，HLD 全部覆盖（代价是代码更长）。

5.12.4 树上启发式合并（dsu on tree）

换一类问题

🎨 题目：数颜色 一棵 n 个节点的有根树（n ≤ 2×10⁵），节点 u 有颜色 col[u]。对每个节点 u，问以 u 为根的子树中共出现多少种不同的颜色。

暴力： 对每个 u DFS 一遍自己的子树，用 cnt[] 数组数颜色——O(N²)，2×10⁵ 规模下超时。

HLD + 线段树？ 不好做——"颜色种数"不是线段树容易合并的信息（合并两段时无法从左右子树的答案推出总颜色数）。

新思路：借用"轻重"的智慧。 每个 u 的答案由它的所有儿子子树合并而来。合并时保留重儿子的统计结果，丢弃轻儿子的：

1. 递归处理每个轻儿子，算出它的答案，然后清空它留下的计数（不保留）；
2. 递归处理重儿子，保留它的 cnt[] 计数；
3. 重新暴力加入所有轻儿子子树的节点（把贡献补回来），再加上 u 自己，得到 ans[u]；
4. 若 keep == false，再把整棵子树的贡献清掉，留给父节点一个干净的计数数组。

为什么是 O(N log N)？

回忆性质 2：从根到任意节点的路径上至多 O(log N) 条轻边。一个节点只有在"作为轻儿子的子树成员被重新加入"（第 3 步）或"被清空"（第 4 步）时才被多花费时间，而它到根的路径上至多 O(log N) 条轻边，所以每个节点最多被"额外处理" O(log N) 次，总计 O(N log N)。

代码（solve(u, keep) 模式）

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 200005;
vector<int> g[MAXN];
int n;
int col[MAXN], sz[MAXN], big[MAXN];
int L[MAXN], R[MAXN], Node[MAXN], totdfn;   // 子树的 DFS 序区间 [L[u], R[u]]
int ans[MAXN], cnt[MAXN], totColor;

void add(int u) {
    if (cnt[col[u]] == 0) ++totColor;   // 新颜色登场
    cnt[col[u]]++;
}
void del(int u) {
    cnt[col[u]]--;
    if (cnt[col[u]] == 0) --totColor;   // 某颜色绝迹
}

void dfs0(int u, int p) {               // 求 sz / big / DFS 序
    L[u] = ++totdfn;
    Node[totdfn] = u;
    sz[u] = 1;
    for (int v : g[u]) if (v != p) {
        dfs0(v, u);
        sz[u] += sz[v];
        if (!big[u] || sz[big[u]] < sz[v]) big[u] = v;
    }
    R[u] = totdfn;
}

void dfs1(int u, int p, bool keep) {    // ★ dsu on tree 主体
    // 第 1 步：轻儿子，算完就清
    for (int v : g[u]) if (v != p && v != big[u]) dfs1(v, u, false);
    // 第 2 步：重儿子，保留计数
    if (big[u]) dfs1(big[u], u, true);
    // 第 3 步：轻儿子子树的节点重新加入（DFS 序连续，直接扫区间）
    for (int v : g[u]) if (v != p && v != big[u])
        for (int i = L[v]; i <= R[v]; i++) add(Node[i]);
    add(u);
    ans[u] = totColor;
    // 第 4 步：不保留则把整棵子树清干净
    if (!keep)
        for (int i = L[u]; i <= R[u]; i++) del(Node[i]);
}

int main() {
    // 7 节点测试树，颜色：1 2 1 2 3 3 3
    n = 7;
    int us[] = {1,1,2,2,3,6}, vs[] = {2,3,4,5,6,7};
    int cs[] = {1,2,1,2,3,3,3};
    for (int i = 0; i < 6; i++) { g[us[i]].push_back(vs[i]); g[vs[i]].push_back(us[i]); }
    for (int i = 1; i <= 7; i++) col[i] = cs[i-1];

    dfs0(1, 0);
    dfs1(1, 0, false);
    for (int i = 1; i <= n; i++) printf("%d%c", ans[i], " \n"[i == n]);
    return 0;
}

运行输出：

3 2 2 1 1 1 1

手算验证：子树 1 含颜色 {1,2,3} → 3；子树 2 = {节点2,4,5}，颜色 {2,3} → 2；子树 3 = {3,6,7}，颜色 {1,3} → 2；子树 4/5/7 单节点 → 1；子树 6 = {6,7}，颜色 {3} → 1。全部吻合。

💡 dsu on tree 的适用信号： "对每个节点统计子树内的信息 + 信息不易用数据结构合并（颜色种数、出现次数最多的颜色的和、合法路径条数等）+ 无修改操作（离线）。三者齐备时，它是代码量最小的 O(N log N) 解法——经典题 Lomsat gelral（CF600E，子树众数颜色之和）就是模板题。

5.12.5 三种树上工具对比

选择口诀：

• 问路径 + 要在线修改 → 重链剖分；
• 只问子树 + 修改简单 → 欧拉序 + BIT（代码短、常数小）；
• 对每个节点都要子树答案 + 信息难合并 + 无修改 → dsu on tree。

⚠️ 常见错误

1. 跳链比较写反： if (dep[top[u]] < dep[top[v]]) swap(u, v); 的目的是让 u 的链顶更深（先跳深的）。写成 dep[top[u]] > dep[top[v]] 会导致跳过 LCA、答案错乱。同理，同链后取 dep[u] > dep[v] 时 swap 后 u 是 LCA——别把方向搞反。

2. 线段树用原编号而不是 dfn 序： build 时叶节点权值应是 val[rnk[l]]，单点修改的位置是 dfn[u] 而不是 u。树剖把树"重排"了，线段树维护的是 dfn 序上的序列。

3. dfs2 忘了重儿子优先： 先递归轻儿子再递归重儿子，链上 DFS 序不连续，查询区间全是错的。dfs2(son[u], t) 必须放在轻儿子循环之前。

4. dsu on tree 忘了清轻儿子： 第 1 步递归轻儿子必须传 keep=false，否则 cnt[] 里残留着轻儿子子树的颜色，父节点的统计会重复计数。

5. 清空用 memset 而不是按子树大小遍历： keep=false 时清空必须 for (i = L[u]; i <= R[u]; i++) del(Node[i]);——只花 O(子树大小)。若对整个 cnt[] 做 memset，每次是 O(值域)，总复杂度退化成 O(N · 值域)，直接超时。

📋 章节小结

📌 核心要点

❓ 常见问题

Q：重链剖分和第 5.13 章的欧拉序有什么区别？
A：欧拉序只保证子树是连续区间；重链剖分用"重儿子优先"的 DFS，额外保证每条重链也是连续区间，所以能处理路径。

Q：跳链求 LCA 和倍增 LCA 用哪个？
A：写了树剖就顺手用跳链——不用额外数组、常数更小；没写树剖就用倍增。两者查询都是 O(log N)。

Q：dsu on tree 能处理带修改的问题吗？
A：不能（标准形式）。需要在线修改时考虑 HLD + 数据结构，或更高级的树上莫队。

🔗 与后续章节的联系

• [第 5.13 章（欧拉游览）： 子树查询的轻量方案；HLD 是它的超集。
• Platinum 点分治： 以树的重心递归分割，把路径问题降到 O(N log² N)——本章 5.12.1 是直接前置。
• [第 5.7 章（线段树）： HLD 的"发动机"，区间合并的性质决定能维护什么信息。

🏋️ 练习题

🟢 简单

5.12-E1. 找重心
给定 N 个节点的树，输出树的重心节点编号（若有多个，输出编号最小的）。
数据规模： 1 ≤ N ≤ 10⁵。

🟡 中等

5.12-M1. 路径最大值 （USACO 风格）
N 个节点的带权树。两种操作：CHANGE x w 修改点权；QMAX u v 查询 u 到 v 路径上点权的最大值。
数据规模： N ≤ 3×10⁴，操作数 Q ≤ 2×10⁵，权值 ≤ 10⁹。

🔴 困难

5.12-H1. 子树颜色数 （CF600E / 数颜色）
N 个节点的有根树，节点 u 有颜色 c[u]。对每个节点 u，求 u 的子树中出现次数最多的颜色编号之和（多个颜色并列时全加）。
数据规模： 1 ≤ N ≤ 10⁵，1 ≤ c[u] ≤ N。