说实话在遇到“把树上一条路径的权值全部加上某个数再问路径上最大最小值”这种需求之前我一直觉得树链剖分是个“又长又麻烦”的算法宁可一辈子只用倍增 LCA。直到后来被一道题逼到墙角我才真正把它捡起来然后发现这套东西一旦理解透了不仅 LCA 可以顺手算路径修改、子树修改、路径极值查询全都能用一种统一的方式搞定而且复杂度稳定在 O(log^2 n) 级别比很多花里胡哨的做法都靠得住。这篇文章我就准备把树链剖分和它支持的 LCA 查询掰开揉碎讲一遍。内容会从最基础的“重儿子”概念讲起逐步走到完整模板和调试技巧。不管你是刚学 LCA 想换套工具的入门者还是已经在用树链剖分但经常被边界条件折磨的老手这篇文章里都有你需要的干货。1. 设计思路树链剖分凭什么能解决 LCA1.1 从“重儿子”开始聊剖分树的剖分有很多种最常见也最常用的是“重链剖分”。它的核心动作其实非常朴素对于树上的每个节点找到它子树大小最大的那个儿子把这个儿子标记为“重儿子”连接它俩的边就是“重边”其他儿子和连边就是“轻儿子”和“轻边”。然后从根开始一路沿着重儿子走下去形成一条条完整的重链。为什么偏偏要挑“子树最大的儿子”这里的关键在于一个很优美的性质从一个节点出发只要走一条轻边跳到父节点的另一侧新子树的规模至少会缩小一半。因为轻儿子的大小永远不会超过父节点所有儿子大小总和的一半以上否则它就会被选成重儿子。这意味着任何一个节点到根节点的路径上轻边数量不会超过 log2(n) 条。换句话来说从任意节点向上跳最多经过 log n 条链就能抵达根。这个性质是整棵树链剖分复杂度分析的地基。我第一次看到这个证明时觉得太妙了它把一个看起来很“工程化”的划分方法直接和 O(log n) 的复杂度挂钩。你不需要担心某个极端链式树会不会退化成 O(n)因为哪怕是链式结构重链本身就覆盖了整条链一次跳完而如果是满二叉树轻边也最多跳到 log n 层。1.2 剖分如何把树上跳跃变成“跳链”树链剖分处理 LCA 的思路和倍增完全不同。倍增是一步步往上跳准确说是按 2 的幂次跳而树链剖分是一段段往上跳每次都把当前节点所在的整条链作为一段直接跳到链头的父亲节点。什么意思呢假设要查询节点 u 和 v 的 LCA。我先看 u 和 v 各自属于哪条链如果不在同一条链上就让“链头深度更深”的那个节点跳到链头然后再跳到链头的父亲。重复这个过程直到两个节点最终落到同一条链上。这时候深度更浅的那个就是 LCA。举个例子某棵树有两条链链头分别是 a 和 b深度相同。u 在 a 链上v 在 b 链上。那么第一次跳的时候因为两者链头深度一样随便选一个跳比如先跳 uu 变成 a 的父亲此时 u 可能已经跑到根或者别的链上。继续比较直到二者在某条链上相遇。整个过程不会跳原始父亲节点而是直接跨过一整条链这就是它快速的原因。这种“把树切成段每段一条链”的思想不仅解决 LCA而且给我们后续做路径查询提供了天然依据。因为重链上的节点在 DFS 序里是连续的一段一段段跳链的过程其实就等价于把树上路径拆成了若干个连续区间这就是树链剖分能配合线段树的根本原因。1.3 对比倍增 LCA我为什么推荐树链剖分很多新手会先学倍增 LCA预处理一个 up[u][k] 数组表示 u 向上走 2^k 步的祖先。这个做法非常直观代码也不难单次查询 O(log n)。但它有个明显的短板如果题目要求“路径上的节点权值全部加 1”倍增就瞬间不会玩了你总不能把路径上每个点的 up 数组都改一遍吧。树链剖分天然补上这个缺口。它把路径问题转换成区间问题配合线段树或者树状数组就能支持修改和查询。另外树链剖分的预处理只需要两遍 DFS复杂度是 O(n)比倍增的 O(n log n) 预处理还少一个 log。当然它的代码量确实比倍增长可当你需要处理树上路径问题时这就是“一份代码解决一类问题”的典型代表。2. 核心预处理两遍 DFS 拆解到骨子里2.1 dfs1搞定 fa、dep、siz、son 四个数组第一遍 DFS 的任务非常明确计算每个节点的父亲 fa、深度 dep、子树大小 siz、重儿子 son。很多人做这步的时候容易犯一个排序错误因为重儿子依赖子树大小所以必须先递归完所有子节点再回头比较 siz 并确定 son千万不能在递归之前就决定谁是大儿子。我来放一个最直接的中文注释版代码这是我在实际代码里一直用的风格void dfs1(int u, int f) { fa[u] f; dep[u] dep[f] 1; siz[u] 1; int maxSiz 0; for (int v : g[u]) { if (v f) continue; dfs1(v, u); siz[u] siz[v]; // 找子树最大的儿子作为重儿子这里必须先递归完 if (siz[v] maxSiz) { maxSiz siz[v]; son[u] v; } } }代码本身不复杂但参数f的传递要小心。我第一次写的时候在循环里没跳过滤掉父节点 v f导致递归死循环。树的结构是无向图必须靠这个条件防止往回跑。还有一个细节dep 数组用 dep[f] 1 计算即可不需要额外递归深度参数。这里的关键是为了后续比较链头深度时用顺序一定不能反。2.2 dfs2分配 dfn、top 和 rnk第二遍 DFS 负责把树映射成一个可以让线段树处理的序列。它做的事情是给每个节点编一个 DFS 序 dfn同时记录每个节点所属链的链头 top。这里有个绝大部分人都会忽略的细节必须先走重儿子再走轻儿子。为什么要这样因为重链上的节点需要出现在连续的一段 dfn 区间里。如果先走轻儿子那么一条重链上的节点在 dfn 里会被其他子树的节点隔开链就变成“断断续续”的了后续区间查询直接失效。标准写法如下void dfs2(int u, int tp) { top[u] tp; dfn[u] timer; rnk[timer] u; // rnk 用于从 dfs 序映射回原节点 if (son[u] 0) return; // 叶子节点没有重儿子 dfs2(son[u], tp); // 重儿子继承当前链头 for (int v : g[u]) { if (v fa[u] || v son[u]) continue; dfs2(v, v); // 轻儿子另起一条链 } }top数组的作用就不用多解释了它是跳链操作的标志物。rnk数组非常容易被新手遗忘当你要对节点做初始化时线段树叶子位置存的应该是原树上的点权值而 dfn 只是一个从 1 到 n 的编号你无法直接知道 dfn 为 5 的点原来是谁所以需要 rnk[dfn[u]] u 来反推。2.3 一条链 一段连续区间经过 dfs2 之后树上每条重链的节点在 dfn 里都是连续的一段。举个例子假设有一条链root - a - b它们会依次得到 dfn 值比如 1、2、3。查询从 root 到 b 的路径就等价于查询 dfn 区间 [1, 3]。这个“链变区间”的映射是整个算法最值钱的地方。它把树上任意两个节点之间的路径拆成了不超过 O(log n) 段连续的 dfn 区间。比如 u 和 v 不在同一链上我们就不断让深度更深的链头往上跳每跳一次就产生一个 [dfn[top[u]], dfn[u]] 区间最后收尾时再产生最后一段区间。打个生活化的比方你要从一栋楼的 5 楼走到另一栋楼的 3 楼正常做法是一层层走倍增 LCA 相当于让你一次跨 2 的幂次层而树链剖分是给你坐电梯每部电梯直接到某一层链头然后换乘下一部。电梯数量很少所以走完很快。3. 实操环节LCA 查询与路径区间操作的完整实现3.1 完整 C 模板我会直接复制进工程里的版本下面这个模板是我个人整理过很多次的最终版本兼顾了清晰度和性能。它支持直接求 LCA、路径点权查询、以及配合线段树的路径修改。我建议你别急着背先跟着 3.2 和 3.3 节的思路过一遍再回头整理成自己的模板。#include bits/stdc.h using namespace std; const int MAXN 100005; vectorint g[MAXN]; int fa[MAXN], dep[MAXN], siz[MAXN], son[MAXN]; int top[MAXN], dfn[MAXN], rnk[MAXN], timerCnt; // ---------- 第一遍 DFS基础信息 ---------- void dfs1(int u, int f) { fa[u] f; dep[u] dep[f] 1; siz[u] 1; int maxSiz 0; for (int v : g[u]) { if (v f) continue; dfs1(v, u); siz[u] siz[v]; if (siz[v] maxSiz) { maxSiz siz[v]; son[u] v; } } } // ---------- 第二遍 DFS剖分 ---------- void dfs2(int u, int tp) { top[u] tp; dfn[u] timerCnt; rnk[timerCnt] u; if (son[u] 0) return; dfs2(son[u], tp); // 先走重儿子 for (int v : g[u]) { if (v fa[u] || v son[u]) continue; dfs2(v, v); // 轻儿子新开一条链 } } // ---------- 纯树链剖分求 LCA ---------- int get_lca(int u, int v) { while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); u fa[top[u]]; } return dep[u] dep[v] ? u : v; } // ---------- 路径查询不用线段树直接用点权数组举例 ---------- // 这里 val[x] 是原始点权通过 rnk 映射到 dfn long long query_path(int u, int v) { long long res 0; while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); // 区间 [dfn[top[u]], dfn[u]] 是当前要处理的一段 // 可以替换为 query_segment(1, 1, n, dfn[top[u]], dfn[u]); for (int i dfn[top[u]]; i dfn[u]; i) res val[rnk[i]]; u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); // 最后一段 [dfn[u], dfn[v]] for (int i dfn[u]; i dfn[v]; i) res val[rnk[i]]; return res; }这里我故意不用线段树先用一个朴素的循环来展示路径被拆成区间的全过程。你在工程中可以直接把循环替换成线段树或树状数组原理完全一样。3.2 拆解 LCA 里的 while 循环这个 while 循环是整个算法最核心的循环之一也是初学者最容易写错的地方。它的执行逻辑是只要 top[u] ! top[v]说明 u 和 v 不在同一条链上。比较两个链头的深度让链头更深的那个节点先跳。为什么要比链头深度因为链头越深说明它离 LCA 越远先抬它更合理。被选中的节点 u直接跳到fa[top[u]]。这一步跳的是整条链链头父亲的深度一定小于当前链头这样就保证 u 永远不会越过 LCA。重复上述过程直到二者同链。同链之后深度较小的那个就是 LCA。注意这里有个很多人常犯的错误比较的是dep[top[u]]和dep[top[v]]而不是dep[u]和dep[v]。如果比较的是节点本身深度你会在某些情况下把一个链头比较浅、但节点很深的位置误判导致跳过头求出错误的祖先。3.3 点权与边权的处理差异上面模板默认处理的是点权。如果题目给的是边权处理办法也很经典把每条边的权值“下沉”到它连接的两个点中深度更深的那个点上。这样一次路径查询就变成对点权数组的查询。但这里有个重要陷阱当你查询 u 到 v 的路径和时真正的边权会落在“除了 LCA 之外的所有节点”上。如果你直接按照点权方式查完整条路径会把 LCA 自己代表的边权也查进去但那根本不是路径上的边。正确做法是路径查询中最后一个区间不再从dfn[lca]开始而是从dfn[son[lca]]开始或者更通用的办法查询[dfn[lca] 1, dfn[深者]]越过了 LCA 代表的边。我在实际工程里一般会先求一次 LCA再分两段查询u 到 LCA 的儿子、LCA 的儿子到 v。这样处理边权语义清晰不容易出 bug。当然在维护链上边权最大值这类问题时犯错的成本很高因为结果只差一个节点肉眼很难看出来。3.4 接上线段树路径修改变成区间修改如果题目要求“对路径上所有节点权值加 w”或者“查询路径最大值”上面的朴素循环就不够用了因为每跳一段链就得遍历一段区间最坏复杂度会退化为 O(n log n)。正确的做法是给每个 dfn 区间配一棵线段树或者树状数组。线段树的建树初始值从哪来非常简单遍历 1 到 n用val[rnk[i]]塞到第 i 个叶子节点。这就是为什么要保留 rnk 数组的原因。路径修改的代码和路径查询非常对称大致如下void update_path(int u, int v, int w) { while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); update_segment(1, 1, n, dfn[top[u]], dfn[u], w); u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); update_segment(1, 1, n, dfn[u], dfn[v], w); }线程树部分我不展开写太多因为它是比较独立的数据结构。但请你记住树链剖分本身只负责“拆路径”真正做区间维护的是线段树。两者是各干各的拆路径的代码和线段树代码是完全解耦的。这样理解你写起来就不会一头扎进去。4. 常见问题与避坑实录4.1 数组边界和栈深度失控树链剖分最常见的崩溃就是数组越界和栈溢出而且二者经常同时出现。数组方面fa/son/top等数组都是开 MAXN没问题。线段树则要开4 * MAXN因为线段树虽然是满二叉树但用数组实现时下标上界接近 4 倍。我见过有人开2 * MAXN结果随机错查了一晚上最后把数组一放大就全好了。栈溢出主要发生在 dfs1 里。如果输入是一棵深度为 10 万的链状树递归直接爆栈。解决办法有几个如果你在 OJ 里可以加栈空间或者用非递归 DFS如果你在自己的项目里最好改成显式栈写法。这里给你个判断标准如果 n 超过 5 万并且递归深度可能接近 n优先考虑非递归否则开在栈上的函数调用会造成不可预测的崩溃。4.2 链头比较和区间方向的混乱我们回到那个高频 bugwhile 循环里比较的到底是链头深度还是节点深度。答案是链头深度。很多人最开始写的是if (dep[u] dep[v]) swap(u, v);然后惊喜地发现很多测试点过了个别测试点挂得很惨。原因在于如果 u 的深度深于 v但 u 所在链的链头极浅剩下路径却很长那么一次性把 u 跳到链头父亲并不会越过 LCA但随后调整的方向可能会乱。整个过程中链头的重要性远大于节点本身。区间方向也容易在路径修改时犯迷糊。记住一个原则在跳链过程中区间永远是 [dfn[top[u]], dfn[u]]并且 u 的深度大于或等于 v 的深度。因为 dfs2 保证了同一链上 dfn 随深度递增所以 dfn[top[u]] 一定小于 dfn[u]不会出现区间左右端点倒置。4.3 边权转移的隐藏坑我们已经说了边权要下沉到子节点。但有个隐藏细节是边权下沉后根节点本身会被赋一个 0 权重它没有父边。如果题目要求区间求和0 完全不影响但如果求的是路径最大值初始化时千万别忘了把根节点设成负无穷否则初始 max 可能就是 0在全是负边权的题里直接翻车。下沉边权的实现也建议独立封装。我第一次做的时候直接拿节点权值数组改了改结果遇到路径修改边权的题发现改一条边的端点会影响两条边逻辑上乱成一团。后来我专门写了一个edgeValToChild的函数处理建图把每条边的权值放到子节点上代码清晰得多。4.4 树链剖分与倍增 LCA 的选型判断和复杂度对照最后来聊一下你到底该用哪个。我整理了一个对照表方便你按题目特征快速选择对比项倍增 LCA树链剖分预处理复杂度O(n log n)O(n)单次 LCA 复杂度O(log n)O(log n)路径点权修改不支持需另想方案支持配合线段树 O(log^2 n)子树修改/查询不支持支持dfn 区间内 O(log n)代码量较短较长多两遍 DFS 和链头逻辑可扩展性差很强所以我的判断很简单如果只求 LCA不涉及任何路径修改倍增就够用别给自己加负担一旦题目出现“路径上所有节点权值加 x”“查询路径最大最小值”“路径第 k 大”这类需求直接上树链剖分。尤其是“子树修改”这个场景很多题目会不知不觉地考它而倍增完全没有招架之力。再从性能上说树链剖分预处理比倍增少了 O(log n)对于 n 很大、询问很多的场景很有优势。单次 LCA 虽然理论复杂度同为 O(log n)但树链剖分常数为小因为它跳的是整条链而不是一个个幂次跳。实际测试中链式结构的树剖 LCA 甚至接近 O(1)。4.5 调试技巧从 dfn 映射到原始节点我把调试经验放在最后讲因为它往往是最难总结的。当你发现树链剖分写出来的答案不对时第一件事不是怀疑线段树而是打印每个节点的 dfn、top、fa、siz。程序跑完两遍 dfs 后构造一个简单的树比如 7 个节点手算一遍期望值再打印实际值比对哪个环节出了问题。具体来说我经常这样打印for (int i 1; i n; i) { printf(node%d fa%d dep%d siz%d son%d top%d dfn%d\n, i, fa[i], dep[i], siz[i], son[i], top[i], dfn[i]); }肉眼看一下重儿子是否选得合理、链头是否一致、同一链上的 dfn 是否连续。如果这些都对了再去检查路径查询中的区间端点。这个方法帮我减少过至少十个小时的无效调试时间。还有一个细节用样例测试时我优先测“查询自己到根节点”“查询两个相邻节点”“查询一条重链上的两个节点”这三类特殊情况。因为三类情况恰好覆盖了 while 循环的三种走向不同链、同链相邻、同链相隔。全部通过之后算法的信心会高很多。树链剖分这套东西学的时候确实比倍增费劲一些但它带来的回报也是长期性的。我个人的体会是把它理解成“把树做成一段一段的电梯”再配合线段树这个“区间操作管家”你在树上的一切路径问题都会变得非常有条理。如果后续你还想挑战“树链剖分 可持久化线段树”或者“动态树”这类进阶话题这套基础逻辑也是绕不开的地基。