树链剖分这块内容我写过很多次模板也看过不少人一上来就背代码结果一换题目就懵。其实这个算法本质上就干了三件事把树拆成链、把链映射成连续区间、然后用线段树去维护这些区间。只要把这条主线想清楚后面所有代码都是顺理成章的。这篇文章我把完整思路、证明过程、实现代码、以及我自己做题时踩过的坑全部写出来一次性聊透。1. 为什么非要“把树掰成链”树上的路径操作到底难在哪1.1 子树问题是简单的路径问题才是硬骨头先回想一个最基本的场景一棵静态的树n 个点你需要支持两种操作给某个节点的子树内所有节点权值加上 x查询某个节点的子树内所有节点权值之和这种题我很早就会做因为它根本用不着树链剖分。只要跑一次 DFS记录每个节点的 dfn 时间戳你会得到一个特别漂亮的结论一棵子树在 dfn 上恰好对应一段连续区间。于是“子树修改 子树求和”就变成了“区间修改 区间求和”拿线段树或者树状数组直接上完事。但问题来了如果操作从“子树”换成“路径”呢比如把 u 到 v 的路径上所有点权值加 x或者查询 u 到 v 路径上的权值最大值。这时候你会发现单纯靠 DFS 序根本撑不住了。一条路径在 dfn 上是东一块西一块的碎片如果你非要把它们拼起来最坏情况下一条路径可能横跨 O(n) 个区间片段暴力做一次操作就是 O(n log n)等于没优化。所以树链剖分解决的核心问题就是怎么把一条路径拆成若干段连续的 dfn 区间而且拆出来的段数要尽量的少。1.2 一个很自然的贪心优先走“大儿子”理解树链剖分最舒服的方式是先别管代码站在出题人的角度想一个问题我有一棵树我想给每个节点分配一个 dfn然后让“树上任意一条路径”拆出来的连续区间的段数尽可能少。我该怎么办最朴素的想法是随便 DFS分配 dfn。但这样的话一条路径可能一会儿跳到这棵子树里一会儿又跳出来区间碎片化严重。这时候就有一个贪心思路如果某条边连接的两个节点是“父子关系”并且这个儿子是父亲所有儿子里子树最大的那个我们就称它为“重儿子”。沿着一路重儿子走下去就形成了一条“重链”。DFS 的时候优先走重儿子让一条重链上的点在 dfn 里尽量靠在一起也就是连续的。这个想法粗看平平无奇但配合一个关键结论整个算法就立住了从任何一个节点出发走到根节点一路上经过的“轻边”条数最多只有 O(log n) 条。这个结论我待会儿在第二章详细证明。你只要先知道它成立就会发现路径拆段的思路呼之欲出从 u 到 v本质上就是两个人各自往 LCA 跳每次跳过一整条重链用一次区间操作跳链的次数是 O(log n) 次所以路径操作就能做到 O(log² n)。1.3 树链剖分解法的主线拆解为了让你后面看代码不迷路我先把整棵技术栈的骨架立在这第一趟 DFS算出每个节点的父节点 fa、深度 dep、子树大小 sz、重儿子 son。第二趟 DFS按照“先重儿子再轻儿子”的顺序分配 dfn每个节点记录它所在重链的链顶 top。维护结构把 dfn 上的序列接到线段树上区间操作都打在这个序列上。路径操作像爬 LCA 一样每次让链顶深度更深的那个节点跳一段区间直到两个点在同一条重链里。这个骨架的变化很少但细节里的坑非常多。我后面会把每一步都拆开讲包括为什么第二趟 DFS 必须先走重儿子跳链时为什么要拿 top 的深度来比这些都会决定你写出来的代码是“能跑”还是“能过题”。2. 轻重儿子的划分艺术重链剖分的贪心原理与复杂度锚点2.1 分清“重儿子”和“重链”别在术语上犯迷糊树的轻重链剖分建立在几个明确定义上。先花三十秒把术语钉死重儿子一个节点的所有儿子中子树大小最大的那个儿子。如果有多个一样大的随便取一个。轻儿子除了重儿子以外的所有儿子。重边父节点连向重儿子的边。轻边父节点连向轻儿子的边。重链连续的重边串起来的一条链通常我们把一个孤立的轻儿子也看作一条重链的起点。注意这里的“重链”有时候也包含单点。实际上代码实现里我习惯把每个轻儿子自身都作为一条新链的链顶所以一条重链要么从根开始要么从一个轻儿子开始。son[u]存的是 u 的重儿子编号top[u]存的是 u 所在重链的链顶节点编号。这两个数组是后面跳链的核心。2.2 关键引理轻边数量为什么只有 O(log n)这是整个树链剖分复杂度成立的“定心丸”我建议你亲手推一遍。设当前在节点 u它有一条轻边连向儿子 v。因为 v 是轻儿子所以 v 的子树大小不可能超过 u 的子树大小的一半。否则 v 就会成为重儿子对吧也就是说sz[v] ≤ sz[u] / 2也就是说每经过一条轻边子树大小至少缩水一半。现在考虑任意一个节点 x从 x 一路走到根节点。这条路上最多能经过多少条轻边呢每次过轻边子树大小 × 1/2而子树大小最小是 1所以轻边的条数最多是 log₂(n) 级别。这个证明虽然简单但它就是树链剖分和倍增法复杂度同级别的原因。而重边呢重边不改变“链顶”的关系走到重边只是继续在同一条重链内移动不产生额外的区间操作。所以我们跳链的时候本质上只在跳轻边而轻边的数量有上界 O(log n)。2.3 为什么第二趟 DFS 必须先走重儿子这一点特别容易被人忽略但它直接影响剖分的正确性和复杂度。第二趟 DFS 要给整棵树分配 dfn。如果我只是普通地 DFS那么一条重链上的点不一定是连续的它们中间会插入大量其他子树。为了做到“一个重链对应一段连续区间”我必须保证在同一条重链内DFS 的访问顺序是连贯的。所以 dfs2 的实现逻辑是先 dfs2(son[u])并且继承当前链顶 top然后再遍历其他轻儿子给每个轻儿子开一条新链链顶就是轻儿子自己。这样重链内部的所有节点dfn 一定是连续的而且父节点的 dfn 一定小于子节点的 dfn。这个顺序保证了后面线段树的区间更新能直接覆盖整条重链。2.4 换一个角度理解复杂度一次路径操作到底做了多少次区间操作把上面两个结论合起来看一次路径操作从 u 跳到 LCA 的过程中每经过一条轻边u 的链顶就换一次我们需要一次线段树区间操作来处理“当前点 u 到当前链顶 top[u]”这一段。因为轻边条数是 O(log n)所以一个方向上的区间操作次数是 O(log n)两个方向合起来也是 O(log n)。每一次区间操作线段树复杂度 O(log n)。于是总复杂度是 O(log² n)。这个复杂度在很多题目里是可以接受的n 到 10^5、操作数到 10^5 都能稳稳跑过。如果是子树操作因为 dfs 序天然连续直接一次线段树区间操作就够了O(log n)。这张复杂度表我在后面选型的时候会再对照一次操作类型树链剖分复杂度预处理O(n)路径修改/查询O(log² n)子树修改/查询O(log n)单点修改O(log n)3. 两次 DFS 与线段树装配一套能直接抄的完整实现3.1 先备好基础数据结构我用链式前向星存图这是一种非常省空间且遍历高效的存法在算法竞赛里基本是标配。两个数组 to 和 nxt配合 head 数组就能存下所有边。然后是一堆全局数组我一个一个说明用途fa[u]父节点。dep[u]深度根节点深度为 1。sz[u]子树大小。son[u]重儿子0 表示没有。dfn[u]u 的时间戳位置也就是 u 在线段树中的下标。rk[i]dfn 的反向映射rk[dfn[u]] u建线段树时把节点权值按 rk 放进去。top[u]u 所在重链的链顶。rk数组非常关键。很多人第一次写树链剖分时建树会写成val[u]但线段树的下标是 dfn不是节点编号。第 5 章我会专门把这个坑拿出来讲。3.2 第一遍 DFS处理祖先关系与重儿子第一遍 DFS 的逻辑很直白从根节点出发算每个节点的 dep、fa、sz并且找到每个节点最大的那个儿子作为重儿子。void dfs1(int u, int f) { fa[u] f; dep[u] dep[f] 1; sz[u] 1; int maxsz 0; for (int i head[u]; i; i nxt[i]) { int v to[i]; if (v f) continue; dfs1(v, u); sz[u] sz[v]; if (sz[v] maxsz) { maxsz sz[v]; son[u] v; } } }注意这里先递归再累加 sz因为子树大小要等子节点返回之后才能算出来。比较 son 的时候用而不是这样即使有两个儿子一样大也只取先遇到的那个不会出问题。这里的复杂度是 O(n)整棵树遍历一遍。3.3 第二遍 DFS剖分链并分配时间戳第二遍 DFS 是最能体现树链剖分“灵魂”的一步。它同时完成了两件事分配 dfn以及确定 top。void dfs2(int u, int t) { dfn[u] timer; rk[timer] u; top[u] t; if (!son[u]) return; dfs2(son[u], t); for (int i head[u]; i; i nxt[i]) { int v to[i]; if (v fa[u] || v son[u]) continue; dfs2(v, v); } }几个细节请你特别注意递归重儿子时top 参数保持不变因为重儿子和当前节点在同一条重链上。遍历轻儿子时dfs2(v, v)每个轻儿子自己开一条新链链顶是自己。判断条件里除了v fa[u]还要排除v son[u]否则重儿子会被遍历两遍。从根节点调用dfs2(root, root)就算完事。调用完之后一条重链上所有节点的 dfn 是连续的并且链顶的 dfn 最小。3.4 线段树按照 dfn 作为下标建树树链剖分的线段树和普通区间操作的线段树几乎一模一样唯一要注意的就是建树初始化的位置。void build(int p, int l, int r) { tr[p].l l; tr[p].r r; if (l r) { tr[p].val val[rk[l]] % MOD; return; } int mid (l r) 1; build(p 1, l, mid); build(p 1 | 1, mid 1, r); pushup(p); }看到val[rk[l]]没有这就是我刚才强调的线段树第 l 个位置存的是 dfn 为 l 的那个节点的原权值。如果不做 rk 映射直接用 val[l]当节点编号和 dfn 不一致时你会得到一堆莫名奇妙的数据。线段树部分我支持区间加、区间求和、区间求最大值都是模板操作。实际题目中需要维护什么信息就把 pushup 和查询函数的合并逻辑改成什么。3.5 路径操作的核心写法跳链合并路径操作是树链剖分里最需要“背逻辑”的地方。核心思路就是两个点不同链时谁的链顶更深谁就先跳一整条链。这里的比较基准是dep[top[u]]而不是dep[u]这个细节很多人写错。void path_update(int u, int v, int add) { while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); update(1, dfn[top[u]], dfn[u], add); u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); update(1, dfn[u], dfn[v], add); } int path_query(int u, int v) { int ans 0; while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); ans (ans query(1, dfn[top[u]], dfn[u])) % MOD; u fa[top[u]]; } if (dep[u] dep[v]) swap(u, v); ans (ans query(1, dfn[u], dfn[v])) % MOD; return ans; }我解释一下循环里的动作如果 u 的链顶比 v 的链顶更深说明 u 还没爬到 v 所在的那条链上那就把 u 从当前位置到链顶这一段整个作为区间操作一次然后 u 跳到链顶的父亲也就是进入上一条链。等两个点进入同一条链之后它们之间的路径就对应 dfn 上一段连续区间直接一次区间操作解决问题。3.6 子树操作的白给写法子树操作反而简单得让人想笑因为 dfn 连续这个性质可以直接用void subtree_update(int u, int add) { update(1, dfn[u], dfn[u] sz[u] - 1, add); } int subtree_query(int u) { return query(1, dfn[u], dfn[u] sz[u] - 1); }为什么区间右端点是dfn[u] sz[u] - 1因为 u 的整棵子树在第二遍 DFS 里是连续访问完的所以它占用的 dfn 正好是dfn[u]到dfn[u] sz[u] - 1。这个性质其实是 DFS 序对任意树都成立的不是树链剖分特有的。只不过树链剖分重排了 DFS 的访问顺序让重链优先但“子树区间连续”依然保持这就够了。4. 高频场景拆解路径操作、子树操作与边权转点权4.1 把链上的区间查询换成区间最值很多同学以为树链剖分只能维护和维护“和”有关的信息其实线段树能维护的信息它都能维护。比如求路径最大值、最小值、异或和、最大子段和只要你的 pushup 把两个儿子区间的信息正确地 merge查询的时候注意把方向信息拼对就行。有一种反直觉的情况需要留意路径查询如果是有方向性的合并比如拼接最大前缀由于跳链是交替从两端跳的最终拼接区间时要反转其中一段的顺序。这一点在做“最大子段和路径查询”这种题时是必踩的坑。比如我现在求路径间最大子段和我会把区间信息抽象成一个结构体包含 sum、lmax、rmax、ans。从 u 往上跳的那些区间放在一个 vector 里从 v 往上跳的区间放在另一个 vector 里最后按顺序合并中间可能还要 swap。如果你用树链剖分做这种题我建议先把方向处理封装成函数别裸着写两段拼接逻辑容易乱。4.2 子树操作配合时间戳的经典应用子树操作最常见的一个背景是“树上染色统计”给一棵有根树支持把一个节点子树内的颜色全部涂成某种颜色或者查询某个子树内有多少种颜色。这类题树链剖分加线段树做起来非常顺因为子树操作只需要 O(log n) 一次区间修改整个算法非常高效。以前我用 DFS 序 树状数组只能做子树求和要想做子树内“颜色种类统计”就会很麻烦因为颜色种类不是一个能用简单区间加法维护的信息。后来把线段树换成维护区间不同颜色数的变种配合 lazy 标记就能搞定。这个场景下树链剖分本质上给你提供了一个“把树上子树问题变成区间问题”的万能入口。4.3 边权转点权最经典的入门应用之一很多题目里权值是挂在边上的而不是挂在点上的。树链剖分只支持维护点权那怎么办有一个非常标准的套路把每条边的权值放到“深度更深的那个端点”上。比如边 (u, v)如果 dep[u] dep[v]那么这条边的权值就记在 point_weight[v] 上。这样做了之后查询路径 u 到 v 边权和就转化为查询路径点权和但有一个关键差别路径上最顶端的那个点不能算。因为那个点对应的边是它的父边根本不在路径上。所以我会给路径查询写两个版本一个版本是“带顶端”一个版本是“不带顶端”。不带顶端的版本在最后的同链收尾区间那里要把左端点从dfn[u]改成dfn[u] 1前提是 u 不是 LCA。实现方式通常是这样在两个点跳到同一条链之后假设当前 u 的深度更浅那么最终的路径区间是[dfn[u] 1, dfn[v]]。如果dfn[u] 1超过了dfn[v]说明路径上没有边了直接不操作。4.4 动态修改边权的处理思路有人会问如果题目要求“修改某一条边的权值”怎么定位这条边对应的点答案是给定一条边 (u, v)判断 dep[u] 和 dep[v]深度更大的那个点就是这条边在点权体系里的对应节点。修改的时候直接 update 那个点的位置。如果是路径修改比如“把路径上所有边权加上 x”那就用不带顶端的路径修改版本每次区间操作之前判断左端点是否要 1。注意修改边权时update的目标位置是dfn[deeper]。这个 deeper 大多数情况下就是当前边两个端点中 dep 更大的那个。5. 我写树链剖分经常翻车的四个细节5.1 建树时数组千万别用错val[rk[l]] 还是 val[l]这个错我第一次写的时候踩得特别惨。树链剖分之后线段树的下标已经变成了 dfn。但节点原本的编号是乱的比如节点 8 的 dfn 可能是 3而节点 3 的 dfn 可能是 10。如果你建树时直接用val[l]那么线段树的第 3 个位置存的是 val[3]但它实际上应该存节点 8 的权值。正确写法是val[rk[l]]因为 rk[3] 8表示 dfn 为 3 的节点是节点 8。这个错通常不会导致程序 RE只会让你答案错得莫名其妙而且很难调试。建议在 build 完树之后先写一个暴力 check随机建一棵树跑一遍所有点的单点查询比对原始权值。5.2 跳链比较深度比的是 top 的深度不是自己的深度很多人第一次写 path_update 的时候会写if (dep[u] dep[v]) swap(u, v);这个写法在普通的 LCA 倍增里是对的但树链剖分跳链里不行。因为我们要决定“谁先跳一整条链”比较的应该是两条链顶的深度链顶越深的它所在的链就“越下方”应该先跳。正确写法是if (dep[top[u]] dep[top[v]]) swap(u, v);那什么时候才能直接用 dep[u] 呢只有当两个点已经在同一条重链里进行最后一次区间操作时才拿 dep 比较谁在上方把深度小的作为区间左端点。5.3 递归深度过大导致爆栈树链剖分的两次 DFS 都是递归实现的。n 到 10^5 的链状树最深递归深度可能达到 10^5在本地或者某些判题环境下会出现爆栈。我曾经在 Windows 上用 Visual Studio 跑深度 2×10^5 的递归直接栈溢出换到 Linux 下加ulimit -s或者写#pragma comment(linker, /STACK:1024000000,1024000000)能解决一部分但最稳妥的方案是改成手写栈的非递归 DFS或者至少把递归函数写成“尾递归”优化友好的形式。不过 OI 和多数 ACM 判题环境对递归深度比较宽容10^5 一般没事。如果你在本地调记得先把栈调大。5.4 边权转点权时最后一段区间别忘了 1这个问题我专门拿出来强调因为它不容易暴露如果你把边权放到深端点上路径查询时最后的[dfn[lca], dfn[v]]区间会把 LCA 的点权也加进去而 LCA 对应的那条边不在路径上。正确写法要判断 LCA 是否位于区间端点。我一般这样处理如果 u 和 v 最后跳到同链令深度小的为 top深度大的为 bottom。若查询边权则查询区间为[dfn[top] 1, dfn[bottom]]若查询点权则为[dfn[top], dfn[bottom]]。两种情况分开写或者封装两个函数。我用一个实际的例子验证一下一条链 1-2-3边权分别放在节点 2 和节点 3 上。查询节点 2 到节点 3 路径上的边权和期望答案是边(2,3)的权值即节点 3 的点权。如果查询区间取[dfn[2], dfn[3]]会把节点 2 的点权也算进去也就是多加了一条边(1,2)的权值。只有从dfn[2] 1开始才正确。5.5 其他容易忽略的实现细节rk数组的命名有人写rev有人写id无所谓但必须保证它和 dfn 的映射关系是反的不能写反。second dfs里要记得先判断if (son[u]) dfs2(son[u], t)否则重儿子是 0 时可能会访问到无效节点。线段树的 lazy 标记更新时不要忘记取模也不要忘记 pushdown。树链剖分的区间修改操作频率很高lazy 写法不对性能会差很多。树链剖分通常配一个取模操作如果题目只要求求最大值把取模去掉可以提升一点常数。6. 到底什么时候该用树链剖分与其他树上算法的选型对比6.1 树链剖分 vs 树上差分 DFS 序树上差分是一个非常轻量级的算法优势是实现简单、常数小但它只适用于“离线 最后一次统一统计”的场景。比如一共给你 m 次路径加值操作最后求每个点的权值树上差分是首选复杂度 O(n m)比树链剖分的 O(m log² n) 快得多。但如果你要的是在线的、修改之后立刻查询树上差分就完全失去作用。树链剖分则可以把“路径修改、路径查询”变成一套在线数据结构的问题这是它最大的不可替代性。所以我的选型经验是所有操作都是离线、最终汇总大胆用树上差分别用树链剖分。操作需要在线或者修改与查询交替出现树链剖分。对比项树上差分 DFS序树链剖分 线段树修改/查询是否在线否离线汇总是单次操作复杂度O(nm) 总复杂度O(log² n)实现复杂度简单较复杂适用场景路径加值最后统计动态修改查询6.2 树链剖分 vs LCTLCT也就是 Link-Cut Tree支持动态加边、删边、换根。如果你面对的树是静态的形态不变那么完全没有必要用 LCT。因为 LCT 代码量大、常量大写起来调试也痛苦。但如果题目要求动态维护森林结构比如支持“连一条边”“断一条边”“查询路径边权和”那树链剖分就无能为力了只能上 LCT。一个反直觉的点LCT 的动态复杂度是 O(log n) 均摊比树链剖分的 O(log² n) 更优但因为常数大实际跑起来 n 10^5 的情况下树链剖分往往比 LCT 快不少。所以在静态树上不要盲目追求“更优复杂度”而选择 LCT。6.3 还有一种情况根本不需要树链剖分如果题目只涉及子树操作那普通 DFS 序 树状数组就够了根本不用写树链剖分。很多初学者总觉得树链剖分万能什么树题都往上写其实没必要。我见过有人用树链剖分做“单点修改 子树查询”的题代码写了 200 行别人用树状数组 50 行搞定这就是杀鸡用牛刀。再用一个例子说明选型思路有一棵静态树需要支持子树内所有点权值加 x查询某个点的权值。这个用树链剖分可以吗可以但完全是浪费。DFS 序 树状数组区间修改单点查询就能解决。只有当操作涉及“路径”并且需要在线处理时树链剖分才真正体现出价值。6.4 树链剖分的另一层价值作为“复杂树上问题”的地基很多更高级的树上算法是构建在树链剖分之上的典型的就是“树链剖分 线段树维护动态 DP”这类组合。比如树上最大权独立集的动态版本直接树形 DP 没法应对修改操作但利用树链剖分把树拆成链在每条链上维护矩阵乘积就能实现单点修改后 O(log² n) 查询全局答案。所以学会树链剖分不只是会一个算法它是通往更高阶动态树上问题的一把钥匙。这个算法值得反复手写几遍直到完全不看板子也能流畅写出来。我自己当年练树链剖分的时候先把洛谷的模板题 P3384 刷了五遍确保基础操作闭着眼睛都能写对。然后去做了几道边权转点权的题把“1”那个细节彻底想透。之后再做那些线段树维护复杂信息的综合题就基本不会再被树链剖分本身绊住了。经验就一句话背代码之前先把为什么这么跳链、为什么这么映射想明白否则遇到变体题你还是在猜。