树链剖分落地手册：两次 DFS + 三个模板 + 换根全解

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki

树上路径查询还在 O(n) 暴力枚举？重链剖分把它压到 O(log²n)。把任意路径拆成 O(log n) 条 DFS 序连续的链段，交给线段树收尾即可。这篇按「拆链 → 模板 → 换根」的顺序，把树链剖分一次讲透。

一张图看懂重链与轻链 🌳

图：一棵树的重链剖分——灰色为子树规模大的重子结点，粗黑边是重边，细边是轻边，绿色框出的连通块即重链

• 每个结点的「重子结点」是子树规模最大（siz 最大）的那个儿子，它和父亲之间是重边；其余儿子是轻子结点，对应轻边。
• 重边首尾相连，把整棵树划成若干条重链；每个结点恰好落在一条链上，落单的结点也算一条链。
• 剖分后按 DFS 序输出，同一条重链上的结点 dfn 必然连续——这是后面所有区间操作的依据。
• 沿任意一条轻边往下走，子树规模至少砍半，所以一条路径上的重链段数不超过 O(log n)：路径查询的复杂度上限由此而来。

两次 DFS 剖分流程

有了定义，剖分本身并不复杂：两趟 DFS，一趟算规模，一趟定链顶和编号。

第一遍 DFS：算子树规模、定重儿子

void dfs1(int u, int f) { fa[u] = f, dep[u] = dep[f] + 1, siz[u] = 1; for (auto v : G[u]) { if (v == f) continue; dfs1(v, u); siz[u] += siz[v]; if (siz[v] > siz[son[u]]) son[u] = v; // 子树最大的儿子 } }

后序处理：子树回溯后累加 siz，顺手记下最大的儿子。一趟搞定父结点、深度、子树规模、重儿子四样东西。

第二遍 DFS：定链顶、压 DFS 序

void dfs2(int u, int ftop) { top[u] = ftop, dfn[u] = ++idx, rnk[idx] = u; if (son[u]) dfs2(son[u], ftop); // 重儿子续链，链顶不变 for (auto v : G[u]) if (v != son[u] && v != fa[u]) dfs2(v, v); // 轻儿子起新链 }

从根出发，重边优先递归：重儿子继承链顶继续往下压 dfn，轻儿子各自当新链起点。这样每条重链在 dfn 上就是一段连续区间，子树也天然连续。预处理到此为止，剩下的全是「区间问题」。

三个高频模板：路径 / 子树 / LCA

预处理完成后，配合任意支持区间修改与区间查询的数据结构（记作seg），三个模板直接复用。

路径查询模板

场景：求 u 到 v 路径上权值和（或最大值，把sum换成max即可）。

int query_path(int u, int v) { int res = 0; while (top[u] != top[v]) { // 不同链：跳较深的链 if (dep[top[u]] < dep[top[v]]) swap(u, v); res += seg.sum(dfn[top[u]], dfn[u]); // 整段链是一次区间查询 u = fa[top[u]]; } if (dep[u] > dep[v]) swap(u, v); res += seg.sum(dfn[u], dfn[v]); // 同一链上补最后一段 return res; }

跳链次数 O(log n)，每段再吃一个 O(log n)，总复杂度 O(log² n)；路径上的最大值、异或等可合并信息同理。

子树查询模板

场景：把 u 的子树整体加一个值，或查询子树权值和。

// 子树 = dfn 上的一段连续区间 seg.update(dfn[u], dfn[u] + siz[u] - 1, w); // 子树加 int res = seg.sum(dfn[u], dfn[u] + siz[u] - 1); // 子树求和

不需要任何树剖技巧，普通 DFS 序就保证子树连续；这里只是复用同一个数据结构。

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] ? u : v; // 同链后较浅者即 LCA }

跳链逻辑和路径查询完全同构，单次 O(log n)，常数比倍增还小。

换根三种情况

路径查询不受换根影响（两点间的简单路径唯一），麻烦都在子树操作上：换根后的「u 的子树」在原始根（比如 1）的 DFS 序下可能不是一段连续区间，得映射回原始树。按 u 和当前根 root 的位置关系分三种。

图：子树操作在序上被划分成若干连续区间的示意——换根后「排除某棵子树」正好对应区间 [1, dfn(v)) 与 [dfn(v)+siz(v), n] 两段

1. u 就是 root：操作对象是整棵树，直接对区间 [1, n] 下手。
2. u 是 root 在原始树上的祖先：记 v 为 u→root 路径上除 u 外的最浅结点，当前树上「u 的子树」= 整棵树 − v 的子树。v 从 root 出发沿重链往上跳，直到dep(top[v]) <= dep[u]+1，再令v = rnk[dfn[top[v]] + dep[u] + 1 - dep[top[v]]]；随后分别操作[1, dfn[v])和[dfn[v]+siz[v], n]两段即可。
3. 其他情况：换根对 u 的子树无影响，照常用[dfn[u], dfn[u]+siz[u]-1]做。

第 2 种情况是树链剖分换根的考点，跳链找 v 的写法建议对着官方模板逐行读一遍。

细节与性能 ⚡

• 底层容器：要区间加/区间和、极值就上线段树，树状数组只够覆盖前缀可合并的场景，别硬套。
• 重链长度可整体预存，给长链剖分继承 DP 数组时按链统一分配内存，省掉大量零散分配。
• 跳链循环本身很轻，主要成本在线段树上；常数敏感时把top/dep/dfn合并进同一层数组访问，比抠位运算划算。

延伸练习

• 「洛谷 P3384」重链剖分模板（区间加 + 路径/子树查询，重链剖分模板的标配套路）
• 「LOJ 139 树链剖分」：换根 + 路径 + 子树全家桶，对应本文换根三种情况
• 「洛谷 P3379」LCA：只用跳链不挂数据结构，专练树链剖分求 LCA

模板代码与逐行讲解见 docs/graph/hld.md，完整参考实现见 docs/graph/code/hld/hld_1.cpp 与 docs/graph/code/hld/hld_4.cpp。

轻边减半，就是树链剖分全部的秘密。

【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki