树链剖分：把大树切成链，轻松找路径
较难23树链剖分详解：把大树切成链，轻松处理路径问题
树链剖分（重链剖分）是一种把树形结构拆成若干条链的算法，配合线段树等数据结构，可以高效地处理树上路径的查询和修改问题。比如：有一棵苹果树，每个节点上有若干个苹果，你想知道从根节点到某个子节点一共经过了多少苹果，或者把整条路径上的苹果数都加一个值。如果直接沿着树枝一个一个节点走，大树可能会很慢（最坏 O(n)），而树链剖分可以把任意路径变成 O(log n) 段连续的区间，然后用线段树一次处理一整段，速度飞快。
核心思想：重儿子与重链
想象你有一棵大树，树有很多分叉。我们要找出每个节点下子树大小最大的那个儿子（称为重儿子），然后把每个节点和它的重儿子连成一条重链。其他儿子（轻儿子）则各自开始一条新的重链。这样做的好处是：任何一条从根到叶子的路径，最多会被不超过 log N 条重链覆盖。这样，处理路径时只需处理每一条重链上的连续区间，而每条重链上的节点在 DFS 序上是连续的，所以可以用线段树快速操作。
生活类比：班级里要选组长。每个同学（节点）手下有若干小弟（子节点）。谁手下的小弟最多，谁就是重儿子（副班长）。然后副班长再选它手下小弟最多的人……这样形成一条骨干链。其他小团体各自独立成组。从班长到任何一个普通同学，最多经过 O(log 班级人数) 个小组长就能找到。
两次 DFS 详解
树链剖分需要两次深度优先搜索（DFS）来收集信息。
第一次 DFS：求父亲、深度、子树大小、重儿子
我们从根节点开始遍历整棵树，记录每个节点的：
fa[u]：父节点dep[u]：深度（根深度为 0 或 1）siz[u]：子树大小（包括自身）son[u]：重儿子（子树大小最大的子节点，如果没有儿子则为 0）
代码示例（假设节点编号从 1 开始，图用邻接表存储）：
void dfs1(int u, int f) {
fa[u] = f; // 父节点
dep[u] = dep[f] + 1; // 深度
siz[u] = 1; // 子树大小初始化为1（自己）
for (int v : G[u]) { // 遍历所有邻接点
if (v == f) continue; // 跳过父节点
dfs1(v, u); // 递归子节点
siz[u] += siz[v]; // 累加子树大小
if (siz[v] > siz[son[u]]) son[u] = v; // 更新重儿子
}
}
第二次 DFS：求链顶、DFS 序（dfn）
第二次 DFS 按照“先重儿子，后轻儿子”的顺序给每个节点分配一个编号（dfn），使得每条重链上的节点编号连续。同时记录每个节点所在重链的顶端 top[u]，以及 rnk[cnt] 表示编号 cnt 对应的原来节点编号。
为什么先走重儿子？ 因为这样可以保证同一条重链上的节点被连续地访问，从而在 dfn 序上形成一段连续的区间。
int cnt = 0; // dfs序计数器
void dfs2(int u, int t) {
top[u] = t; // 当前节点所在重链的顶端
dfn[u] = ++cnt; // 给节点分配dfs序编号
rnk[cnt] = u; // 反向映射
if (!son[u]) return; // 没有重儿子，即叶子节点
dfs2(son[u], t); // 先走重儿子，保持重链连续
for (int v : G[u]) {
if (v != fa[u] && v != son[u]) // 轻儿子
dfs2(v, v); // 轻儿子开始新的一条重链，顶端就是自己
}
}
举例：假设有一棵二叉树：
1
/ \
2 3
/ \ / \
4 5 6 7
假设子树大小：siz[1]=7, siz[2]=3, siz[3]=3, siz[4]=1, siz[5]=1, siz[6]=1, siz[7]=1。对于节点1，重儿子为2（或3，任选最大，这里选2）。对于节点2，重儿子为4（或5，选4）。对于节点3，重儿子为6（或7）。所以重链为：1-2-4，3-6，5，7。第二次DFS会先走1-2-4这条链，分配dfn=1,2,3给1,2,4；然后回溯回来，走轻儿子5，分配dfn=4；再走节点3的重链3-6，分配dfn=5,6；最后走轻儿子7，分配dfn=7。最终dfn顺序为：1,2,4,5,3,6,7。注意重链上的节点dfn连续。
为什么路径被切成 O(log N) 条链？
这是因为每经过一条轻边（从轻儿子出发的边），子树大小至少减半。具体地，如果一个节点不是其父节点的重儿子，那么它的子树大小 ≤ 父节点子树大小的一半。所以从根到任意叶子，最多经过 O(log N) 条轻边，而每条重链之间由轻边连接，因此路径上最多有 O(log N) 条重链。
线段树维护：把树变成连续区间
经过第二次DFS后，树上的每个节点都有了唯一的dfn编号。而且任意一条重链上的节点dfn连续。我们可以用线段树（或树状数组、分块）来维护整个dfn序列上的信息（比如点权、路径和、最大值等）。线段树支持区间查询和区间修改，复杂度 O(log N) 每次操作。
线段树模板（用于路径和查询和区间加修改）：
int seg[MAXN*4]; // 线段树数组，存储区间和
int lazy[MAXN*4]; // 懒标记，用于区间加
void build(int o, int l, int r) {
if (l == r) {
seg[o] = a[rnk[l]]; // a是原始节点权值，注意rnk[l]得到原节点编号
return;
}
int mid = (l+r)/2;
build(o*2, l, mid);
build(o*2+1, mid+1, r);
seg[o] = seg[o*2] + seg[o*2+1];
}
void pushdown(int o, int l, int r) {
if (lazy[o]) {
int mid = (l+r)/2;
seg[o*2] += lazy[o] * (mid-l+1);
seg[o*2+1] += lazy[o] * (r-mid);
lazy[o*2] += lazy[o];
lazy[o*2+1] += lazy[o];
lazy[o] = 0;
}
}
void update(int o, int l, int r, int ql, int qr, int v) {
if (ql <= l && r <= qr) {
seg[o] += v * (r-l+1);
lazy[o] += v;
return;
}
pushdown(o, l, r);
int mid = (l+r)/2;
if (ql <= mid) update(o*2, l, mid, ql, qr, v);
if (qr > mid) update(o*2+1, mid+1, r, ql, qr, v);
seg[o] = seg[o*2] + seg[o*2+1];
}
int query(int o, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return seg[o];
pushdown(o, l, r);
int mid = (l+r)/2;
int res = 0;
if (ql <= mid) res += query(o*2, l, mid, ql, qr);
if (qr > mid) res += query(o*2+1, mid+1, r, ql, qr);
return res;
}
路径查询与修改：跳链操作
现在我们有了线段树，可以快速处理一段连续区间的信息。对于任意路径 (u, v)，我们需要把它拆成若干条完整的重链区间。基本思路是：让 u 和 v 沿着各自的重链向上跳，直到它们位于同一条重链上。每次跳的时候，取当前链顶深度较大的那个节点，处理它所在的整条链（从链顶到该节点），然后跳到链顶的父节点，继续比较。
路径查询（求和）：
int pathQuery(int u, int v) {
int res = 0;
while (top[u] != top[v]) { // 不在同一条重链
if (dep[top[u]] < dep[top[v]]) // 确保u所在链顶更深
swap(u, v);
res += query(1, 1, n, dfn[top[u]], dfn[u]); // 处理整条链的一段
u = fa[top[u]]; // u跳到链顶的父亲
}
// 现在 u 和 v 在同一条重链上
if (dep[u] > dep[v]) swap(u, v);
res += query(1, 1, n, dfn[u], dfn[v]); // 处理最后一段
return res;
}
路径修改（区间加）：
void pathUpdate(int u, int v, int val) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
update(1, 1, n, dfn[top[u]], dfn[u], val);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
update(1, 1, n, dfn[u], dfn[v], val);
}
注意：在最后一段中，dfn[u] 到 dfn[v] 对应的是 u 到 v 的路径（u是深度较小的那个，即较浅的点），之所以包含 u，是因为路径可能包括 u 和 v 的 LCA（最近公共祖先）。如果需要排除 LCA，需要特殊处理。
完整可运行的示例
下面是一个完整的 C++ 程序，实现了树链剖分 + 线段树，支持路径求和与路径区间加。假设有 n 个节点，m 次操作，操作为：
C u v w：路径u-v上所有点权加 wQ u v：查询路径u-v上所有点权之和
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int n, m, root;
vector<int> G[MAXN]; // 邻接表
int a[MAXN]; // 原始点权
// 树链剖分所需数组
int fa[MAXN]; // 父节点
int dep[MAXN]; // 深度
int siz[MAXN]; // 子树大小
int son[MAXN]; // 重儿子（0表示没有）
int top[MAXN]; // 链顶
int dfn[MAXN]; // dfs序编号
int rnk[MAXN]; // 编号到原节点映射
int cnt; // 编号计数器
// 线段树
int seg[MAXN*4]; // 区间和
int lazy[MAXN*4]; // 懒标记
// 第一次DFS
void dfs1(int u, int f) {
fa[u] = f;
dep[u] = dep[f] + 1;
siz[u] = 1;
son[u] = 0; // 初始无重儿子
for (int v : G[u]) {
if (v == f) continue;
dfs1(v, u);
siz[u] += siz[v];
if (siz[v] > siz[son[u]]) son[u] = v;
}
}
// 第二次DFS
void dfs2(int u, int t) {
top[u] = t;
dfn[u] = ++cnt;
rnk[cnt] = u;
if (!son[u]) return; // 叶子
dfs2(son[u], t); // 先走重儿子
for (int v : G[u]) {
if (v != fa[u] && v != son[u])
dfs2(v, v); // 轻儿子另起链
}
}
// 线段树构建
void build(int o, int l, int r) {
if (l == r) {
seg[o] = a[rnk[l]];
return;
}
int mid = (l + r) / 2;
build(o*2, l, mid);
build(o*2+1, mid+1, r);
seg[o] = seg[o*2] + seg[o*2+1];
}
// 下传懒标记
void pushdown(int o, int l, int r) {
if (lazy[o]) {
int mid = (l + r) / 2;
seg[o*2] += lazy[o] * (mid - l + 1);
seg[o*2+1] += lazy[o] * (r - mid);
lazy[o*2] += lazy[o];
lazy[o*2+1] += lazy[o];
lazy[o] = 0;
}
}
// 区间加
void update(int o, int l, int r, int ql, int qr, int v) {
if (ql <= l && r <= qr) {
seg[o] += v * (r - l + 1);
lazy[o] += v;
return;
}
pushdown(o, l, r);
int mid = (l + r) / 2;
if (ql <= mid) update(o*2, l, mid, ql, qr, v);
if (qr > mid) update(o*2+1, mid+1, r, ql, qr, v);
seg[o] = seg[o*2] + seg[o*2+1];
}
// 区间求和
int query(int o, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return seg[o];
pushdown(o, l, r);
int mid = (l + r) / 2;
int res = 0;
if (ql <= mid) res += query(o*2, l, mid, ql, qr);
if (qr > mid) res += query(o*2+1, mid+1, r, ql, qr);
return res;
}
// 路径加
void pathUpdate(int u, int v, int val) {
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) swap(u, v);
update(1, 1, n, dfn[top[u]], dfn[u], val);
u = fa[top[u]];
}
if (dep[u] > dep[v]) swap(u, v);
update(1, 1, n, dfn[u], dfn[v], val);
}
// 路径求和
int pathQuery(int u, int v) {
int 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() {
// 示例输入：
// 第一行：n m root
// 第二行：n个点权
// 接下来n-1行：边
// 接下来m行：操作
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> root;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
// 树链剖分预处理
dfs1(root, 0); // 根的父亲设为0
dfs2(root, root); // 根链顶为自身
build(1, 1, n); // 建线段树
while (m--) {
char op;
int u, v, w;
cin >> op;
if (op == 'C') {
cin >> u >> v >> w;
pathUpdate(u, v, w);
} else if (op == 'Q') {
cin >> u >> v;
cout << pathQuery(u, v) << '\n';
}
}
return 0;
}
新手常见错误
- 忘记更新子树大小
siz：DFS1 中需要先递归子节点再累加siz。 - 重儿子比较条件用错：
if (siz[v] > siz[son[u]])注意son[u]初始为 0，siz[0]未定义，最好在循环外初始化为 0，或者用if (siz[v] > siz[son[u]] || son[u]==0)。 - 第二次 DFS 中忘记递归轻儿子：必须遍历所有非父非重儿子的子节点并对其调用
dfs2(v, v)。 - 跳链时比较深度用错：应该比较
dep[top[u]]和dep[top[v]]，而不是dep[u]和dep[v]，因为我们要确保每次处理的是较深的那条链。 - 线段树区间边界：
dfn从 1 到 n，注意数组大小开 4 倍。 - 路径修改时最后一段的边界：当
u和v在同一条重链上时，需要保证dfn[u] <= dfn[v]且区间覆盖了从较浅点到较深点的所有节点。如果只需要不包括 LCA，则需特殊处理（如u为 LCA 时，从son[u]开始）。 - 多组数据时清空数组：注意清空邻接表和数组，尤其是
son和top。
相关指引
- 子树操作：由于 dfn 序中，一棵子树的所有节点也对应一段连续区间（因为 DFS 进入和离开子树的时间区间），所以也可以直接用线段树处理子树查询和修改，无需跳链。
- 求 LCA：树链剖分可以快速求 LCA（通过不断跳链，直到链顶相同，然后深度小的就是 LCA）。实际上，
pathQuery中的跳链操作就是在寻找 LCA 的过程。 - 树链剖分的其他应用：可以用来维护路径上的最大值、最小值、区间异或、区间取反等，只需修改线段树的操作。
- 与树分块的区别：树分块（如树上莫队）适合离线的路径查询，而树链剖分适合在线的动态修改和查询，且支持区间修改（如给路径加值）。
- 相关算法：树链剖分常与 LCT（Link-Cut Tree）对比，LCT 更灵活但常数大，树链剖分较简单且适合静态树，配合线段树效率高。
掌握了树链剖分，复杂的树上路径问题就变成了熟悉的区间操作，是竞赛中解决树上问题的利器。
例题精讲
在树链剖分中，对于一个节点，其所有子节点中子树节点数最多的子节点称为？
树链剖分中，每个节点到根节点的路径上最多经过O(log n)条重链。
以下为树链剖分第一次DFS的部分代码，请补全找出重儿子的部分：
void dfs1(int u, int f) {
size[u]=1; fa[u]=f; dep[u]=dep[f]+1;
int maxson=0;
for(int v:g[u]){
if(v==f) continue;
dfs1(v,u);
size[u]+=size[v];
if(size[v] > maxson) {
maxson=size[v];
___ = v;
}
}
}树链剖分后，通常使用什么数据结构来维护每条重链上的信息？
树链剖分中，每个节点在链中的位置（dfs序）是连续的，并且同一重链上节点的dfs序也连续。