树链剖分配合LCA是我在树上数据结构这条路上真正开窍的第一个里程碑。最开始翻开题解满屏的 dfn、top、heavy 直接把我看懵了。后来自己把一棵小树完整地在纸上剖了一遍才明白它根本不是多玄妙的东西——它只是非常朴素地告诉你树上的任意一条路径可以被拆成 O(log n) 段连续的区间而连续的区间线段树这类数据结构接得毫不费力。这篇文章我打算用尽量大白话的方式把剖分的原理、两次 DFS 的细节、求 LCA 的完整过程以及我这些年写题踩过的坑一次性讲透。适合有一点树和图 DFS 基础的人至少要知道树的遍历怎么写、递归是怎么回溯的。1. 树上的路径问题到底难在哪1.1 一次朴素查询的真实代价先看一个最常见的场景给一棵 n 个节点的树每个点有点权。要求支持两类操作把 a 到 b 路径上所有点的权值加一个数以及查询 a 到 b 路径上所有点的权值之和。如果第一次接触这类题绝大多数人会写暴力从 a 一步一步往上走到 LCA再从 b 一步一步往上走到 LCA一路上把经过的点全部改一遍或者统计一遍。这个做法本身没有错但它的耗时完全取决于路径长度。当树被故意构造成一条直线时a 和 b 分别取两端的节点一次操作就要遍历 n 个点。操作次数 q 一多总复杂度就是 O(nq)在 n 和 q 都在 10^5 量级的情况下跑完全部数据基本等于不可能。有人会问树上两点路径用倍增法先求 LCA 不也能 O(log n) 吗这里必须分清楚一个概念求 LCA 和修改路径上所有点是两件完全不同的事。倍增法确实能快速告诉你 LCA 是谁但当你要把 a 到 b 之间的所有点都摘出来操作时倍增法帮不上太多忙——你还是得一个点一个点地跳或者在倍增数组里额外维护信息而那样能维护的信息形态非常有限。树链剖分的价值恰恰体现在这里它不仅能求 LCA更重要的是能把一条路径切成若干段连续的区间然后把这些区间依次交给线段树处理。我平时跟人讲这个思路时经常打一个比方地图上两个地点之间的最短距离用公式立刻能算但如果要求你把路径上所有路口都装上摄像头你至少得知道这条路到底经过哪些路口、按什么顺序经过。树链剖分干的事就是给你一张路条清单写着先走这段、再走那段、最后走哪段清清楚楚。1.2 能不能把树拉直我们已经很熟悉一个工具DFS 序。给一棵有根树做深度优先遍历每个点会获得一个访问时间戳。如果题目要求修改以 u 为根的子树中所有点或者查询子树信息利用 DFS 序可以非常舒服地完成因为一棵子树里的所有点在 DFS 序上恰好对应一段连续的编号。那路径呢很遗憾任意一条路径上的点在 DFS 序里大概率是打散的。路径可能一会儿进入某棵子树一会儿又跳出来进入另一棵子树直接基于普通 DFS 序做路径操作完全行不通。不过这个失败给了我们一个重要的启发如果我能人为设计一种编号方式让任意路径都被拆成少数几段连续编号问题就迎刃而解了。树链剖分就是沿着这个思路设计出来的把整棵树拆成若干条链每条链内部的节点编号连续任意一条树上的路径等于若干个完整链段的拼接。你在一条主干道上来回走自然比在迷宫一样的巷子里摸方向快得多。2. 轻重链剖分核心概念一次看懂2.1 重儿子与重链的定义树链剖分有很多流派长链剖分、实链剖分都有各自的应用场景。竞赛和面试里最常见、也最值得先掌握的是轻重链剖分它做决策的核心依据是子树大小。对于一个节点 u假设它有若干个儿子 v1、v2、v3……我们先做一次 DFS把每个儿子的子树大小 sz[v] 都算出来。其中 sz 最大的那个儿子叫 u 的重儿子其余儿子都叫轻儿子。连接 u 与重儿子的那条边叫重边连接 u 与轻儿子的边叫轻边。把若干条连续的重边串起来就形成了一条重链。这里有一个容易忽略的点一个孤立的节点也可以视为一条长度只有 1 的链。这样规定之后整棵树会被完全拆分成若干条互不相交的重链每个节点恰好属于其中一条。还有一个细节顺带提一下如果一个节点有多个儿子的子树大小相同随便选一个当重儿子即可这不影响正确性也不会改变复杂度只是最终剖分出来的链形态可能有细微差别。不需要为了哪个更优纠结程序里只要保证同一棵树的剖分结果是确定一致的就行。为什么偏偏选 subtree size 最大的儿子直观上我们希望那些体量很大的分支尽量待在比较长的链里这样大多数节点都躺在大链上真正需要频繁换链的场景就会变少。后面你会看到正是这个选择直接决定了跳链次数的上界。2.2 轻边数量的上界复杂度自信的根源树链剖分最核心、最漂亮的性质是从根节点走到任意一个节点途经的轻边数量不超过 O(log n)。第一次看到这个结论的人往往会觉得不可思议但证明其实非常短。假设当前走到了节点 u下一步要通过一条轻边走到它的轻儿子 v。注意 v 是轻儿子说明 u 的重儿子的子树大小至少不小于 sz[v]。那么我们可以写一个非常简单的不等式设 u 的重儿子为 r则 sz[v] ≤ sz[r]。同时v 和 r 都是 u 的不同儿子它们两个的子树合起来再加上 u 自己才构成 u 的整棵子树所以 sz[r] sz[v] ≤ sz[u] - 1。把两个不等式合并得到 2 × sz[v] ≤ sz[u] - 1也就是 sz[v] sz[u] / 2。这就是关键每经过一条轻边所在的子树大小至少缩水一半。那么从根出发最多经过 floor(log2 n) 条轻边当前所在子树的规模就会缩小到 1也就是抵达叶子节点。所以根到任意节点的路径上轻边数量是 O(log n)。有了这个性质整个树剖的复杂度就有了底气任意一条从 a 到 b 的路径可以看作 a 到 LCA 再接 b 到 LCA 两段。每一段里轻边的数量都不超过 O(log n)意味着我们在处理路径时最多需要切换 O(log n) 次链。这个 log 级别的上界就是所有基于树剖做路径操作的数据结构的复杂度根基。2.3 剖分过程中需要维护哪些数组写树剖模板前最好先把下面这些数组的含义全部背熟。它们就是剖分的全部家当。数组名含义由哪一遍 DFS 得到fa[u]u 的父亲节点编号第一遍depth[u]u 的深度根深度为 1第一遍sz[u]以 u 为根的子树的节点总数第一遍heavy[u]u 的重儿子编号0 表示没有第一遍top[u]u 所在重链的链头节点第二遍dfn[u]u 剖分后获得的新编号第二遍rnk[i]新编号 i 对应的原树节点第二遍最后这个 rnk 数组经常被初学者忽略但它非常关键。因为后续线段树或者树状数组管理的区间是基于 dfn 编号的段树里存的是 dfn 序上的信息当我们需要知道线段树里第 i 个位置到底对应原树的哪个节点时就必须借助 rnk 反查回去。这一步如果漏了代码会在各种意想不到的地方爆出错。我记得早期自己写树剖题时犯过一种很典型的错误线段树明明管的是 dfn 区间我却在查询时稀里糊涂地用了原节点编号去访问线段树结果样例都能过、一到正式数据就 WA 到崩溃。这种 dfn 与原始编号混淆的问题几乎是每个顺手写过树剖的人都会经历的阶段后面的答疑部分我会专门再讲。3. 两次DFS从理论到第一行代码3.1 第一遍DFS统计家族信息第一遍 DFS 的任务是摸底把每个节点的父亲、深度、子树大小和重儿子全部统计出来。代码如下void dfs1(int u, int father) { fa[u] father; depth[u] depth[father] 1; sz[u] 1; int max_sz 0; for (int v : g[u]) { if (v father) continue; dfs1(v, u); sz[u] sz[v]; if (sz[v] max_sz) { max_sz sz[v]; heavy[u] v; } } }细节一sz[u] 初始化为 1代表节点 u 自身。DFS 回溯时把每个儿子的 sz 累加进来就得到了完整的子树大小。这个递推关系是所有后续判断的基础。细节二max_sz 初始为 0。如果 u 是叶子节点循环里一个儿子也不会进入heavy[u] 会保持为 0表示没有重儿子。我建议全模板统一用 0 表示空节点原因后面会在避坑部分展开。细节三整个第一遍 DFS 必须理解成后序处理——先递归下去把儿子的信息算完回溯时再汇总到父节点。如果你把更新 sz 和 heavy 的代码写在递归之前那 sz[v] 还是初始状态整个逻辑就全乱了。3.2 第二遍DFS分链与编号第二遍 DFS 的任务是切链把树重新组织成若干条重链同时给每个节点分配一个新的编号 dfn。这一段是整个剖分里最需要仔细理解的部分。void dfs2(int u, int t) { top[u] t; dfn[u] timer; rnk[timer] u; if (heavy[u] 0) return; // 叶子节点直接结束 dfs2(heavy[u], t); // 优先走重儿子保持同链编号连续 for (int v : g[u]) { if (v fa[u]) continue; if (v heavy[u]) continue; dfs2(v, v); // 轻儿子作为新链的链头 } }关键在倒数第三行的先走重儿子。为什么这条顺序如此重要因为我们要保证同一条重链上的节点dfn 编号是连续的。只有先递归重儿子把整条重链一口气排完这条链上的节点才会在编号上形成一整段。你可以想象整理书架你希望同一套丛书的所有册数挨在一起那就要先把这一套书完整地摆好再去摆下一套。如果摆完一本就插一本别的书同一套丛书就被打散了。树剖同理同一条链的节点编号如果不连续后面线段树按区间操作时就会破坏整段区间。处理完重儿子之后再依次处理轻儿子。每个轻儿子都以自己作为新链的链头所以传入 dfs2(v, v)。至于整棵树的第一个调用直接写 dfs2(1, 1)根节点就是第一条重链的链头。3.3 用手推一个小树把剖分看一遍光看代码容易虚空我们拿一棵只有 7 个节点的树手动完整地剖一遍。树的形态如下根节点是 1它有儿子 2 和 3节点 2 有儿子 4 和 5节点 3 有儿子 6节点 5 有儿子 7先跑第一遍 DFS。我们按输入顺序假设进入 1 后先访问 2。7 是叶子sz[7]15 的子树包含自己和 7所以 sz[5]24 是叶子sz[4]1。那么节点 2 的两个儿子子树大小分别是 1 和 2其中更大的是 5因此 heavy[2]5。节点 3 那边6 是叶子sz[6]13 唯一的儿子就是重儿子所以 heavy[3]6。最后看根节点 1儿子 2 的子树大小为 3包含 2、4、5、7儿子 3 的子树大小为 2包含 3、6所以 heavy[1]2。第二遍 DFS 从 dfs2(1, 1) 开始。访问 1dfn[1]1top[1]1。接着优先走重儿子 2dfn[2]2top[2]1。2 的重儿子是 5继续走dfn[5]3top[5]1。5 的重儿子是 7继续走dfn[7]4top[7]1。此时整条链 1-2-5-7 排完了编号是 1、2、3、4。回到节点 2处理轻儿子 4dfn[4]5top[4]4这条链只有它一个节点。再回到根节点 1处理轻儿子 3dfn[3]6top[3]3。3 还有重儿子 6继续走dfn[6]7top[6]3链 3-6 排完了。最终剖分结果非常清晰链 11-2-5-7链头 1编号 1, 2, 3, 4链 24链头 4编号 5链 33-6链头 3编号 6, 7你可以观察到一个现象每条链上的编号都是连续的这就是第二遍 DFS 中先重后轻策略的功劳。同时还有一个额外的福利任意一个节点的子树在 dfn 序上依然是连续区间。比如节点 2 的子树包含 2、4、5、7对应编号 2、3、4、5正好是区间 [2,5]。这个性质在后面的子树操作里会直接用到。4. 树链剖分求LCA跳跃的艺术4.1 为什么剖分之后LCA变得这么容易树链剖分完成之后求两个点的 LCA 从一步一步往上爬升级成了一条链一条链地跳。先考虑最简单的情形如果 a 和 b 已经在同一条重链上那它们之间的祖先关系是确定的深度更小的那个就是 LCA。在同一链上的两点之间是一段连续的祖先-后代关系取深度较小的那个自然没问题。如果 a 和 b 不在同一条链上呢此时让它们跳链。具体来说比较 top[a] 和 top[b] 的深度谁的链头更深就说明谁离 LCA 更远那就把整个链头所在的链条跳过去——直接把那个节点改成链头的父亲 fa[top[x]]。然后重复这个比较直到两个点落到同一条链上。为什么每次跳一整条链是安全的因为 LCA 不可能藏在这种被整条跳过的深层链上。如果 a 所在链的链头 top[a] 深度比 top[b] 更深那 a 和 b 的 LCA 一定还在 top[a] 的上方这个链头以及它下方的整条链都不可能同时包含 b 那边的路径所以 a 可以直接跳到链头的父亲不会跳过 LCA。这个过程跟手动求 LCA 时的直觉一致谁位置更深谁往上走。只不过树剖把走一步升级成了走一整条链。每次跳链本质上都会跨过至少一条轻边前面我们已经证明过从任意点出发到祖先的路径上轻边总数是 O(log n)所以整个 while 循环的次数也稳定在 O(log n)效率有足够保障。4.2 代码实现与手推样例直接上代码非常短int lca(int a, int b) { while (top[a] ! top[b]) { if (depth[top[a]] depth[top[b]]) { swap(a, b); } a fa[top[a]]; } return depth[a] depth[b] ? a : b; }不少初学者看到这个 while 循环能理解但看到最后那个 return 又会愣一下为什么跳出循环了还要比一次深度原因是 while 循环结束时a 和 b 已经位于同一条重链上了。既然在一条链上它们必然是一上一下的祖先关系深度小的那个就是 LCA。直接比较两个点的深度返回较浅的那个即可。我们用第 3 章那棵树手动跑一遍 lca(7, 6)。初始 a7b6。top[7]1top[6]3不相等。 比较 depth[top[a]]depth[1]1 和 depth[top[b]]depth[3]2前者更浅于是交换当前 a6b7。 执行 afa[top[6]]fa[3]1。现在 a1b7。top[1]1top[7]1相等跳出循环。 比较 depth[1]1 和 depth[7]4返回 1。LCA 是 1正确。再试一组 lca(4, 7)。初始 a4b7。top[4]4top[7]1不相等。 比较 depth[4]2 和 depth[1]1前者更大不交换直接 afa[top[4]]fa[4]2。 现在 a2b7top[2]1top[7]1相等跳出循环。 比较 depth[2]2 和 depth[7]4返回 2。LCA 是 2正确。强烈建议你多选几组点在纸上把每一步的 a、b、top、depth 全部写下来。我第一次完整跳明白这个流程之后后面的路径操作基本就是照葫芦画瓢了。4.3 和常见LCA方法放在一起比一比可能有人会问我本来就会倍增法求 LCA为什么还要学树剖实际上这两个方法是不同场景下的不同工具。我把主流的 LCA 解法拉到一个表里对比这样差异一眼就能看清方法预处理复杂度单次查询能否维护路径信息倍增法O(n log n)O(log n)较难能维护的信息很有限Tarjan 离线O(n q)需离线处理无法在线修改树链剖分O(n)O(log n)可以直接配合线段树做区间操作RMQ 欧拉序O(n log n)O(1)无法直接维护路径修改看出区别了吗树链剖分的预处理甚至比倍增还便宜只需要 O(n) 的时间就能完成两遍 DFS查询也有 O(log n) 的单次复杂度。更重要的是它天然给出了路径对应的链段拆分方案这才是做路径修改和路径查询的核心能力。如果你只是单纯求 LCA不涉及任何修改操作那我承认倍增法甚至 RMQ 都更省事但一旦题目要求改路径上的点权或查路径上最大值/和树链剖分几乎是绕不开的正解。竞赛中树链剖分 线段树是一整套非常成熟的组合技学会树剖求 LCA 只是第一步往上一小步就是路径操作性价比非常高。5. 不只是LCA树剖的威力在路径操作5.1 路径加、路径求和先拆成O(log n)个区间树链剖分最经典的落地应用是支持路径上所有点权值加一个数以及查询路径上所有点权值之和。思路跟求 LCA 几乎一致每次进入 while 循环把当前这条链上的那一段区间交给线段树做一次区间修改或区间查询然后把节点跳到链头的父亲。唯一需要额外小心的是最后 a 和 b 落到同一条链上时要把深度小的那个放在区间左端因为线段树的区间操作要求左端点编号小于右端点。void path_add(int a, int b, int val) { while (top[a] ! top[b]) { if (depth[top[a]] depth[top[b]]) { swap(a, b); } seg.update(dfn[top[a]], dfn[a], val); a fa[top[a]]; } if (depth[a] depth[b]) { swap(a, b); } seg.update(dfn[a], dfn[b], val); } int path_query(int a, int b) { int res 0; while (top[a] ! top[b]) { if (depth[top[a]] depth[top[b]]) { swap(a, b); } res seg.query(dfn[top[a]], dfn[a]); a fa[top[a]]; } if (depth[a] depth[b]) { swap(a, b); } res seg.query(dfn[a], dfn[b]); return res; }对比一下第 4 章的 LCA 代码你会发现结构几乎是一个模子刻出来的区别只有两点一是对 dfn 区间额外执行了线段树操作二是最后同链时处理最后一段区间。这里有一个关于方向和顺序的提醒路径本身是 a 到 LCA 再到 b 的折线但我们在拆区间时并不关心每一段的方向因为普通权值加和的运算具有交换律。不过如果你要维护的信息是有方向性的比如边权差、颜色段数量、区间翻转等那就必须仔细考虑区间合并的顺序了。这类有向信息的维护难度会高出不少建议初学时先把无方向的路径和彻底吃透再往深走。5.2 子树操作剖分留下的彩蛋你在第 3 章手推剖分时应该已经注意到在 dfn 编号方式下一棵子树在树上的所有节点其编号是连续的。这时候修改以 u 为根的子树上所有点权就变成了一次简单的线段树区间操作。void subtree_add(int u, int val) { seg.update(dfn[u], dfn[u] sz[u] - 1, val); }一行代码就能搞定子树修改。这也让树剖 线段树的组合拥有两套能力路径操作走跳链 区间操作子树操作直接走区间操作。真正做难题时这两种操作往往会在同一道题里同时出现非常常见。顺带说一句如果你只做子树相关的问题普通 DFS 序就能满足没必要动用树剖。树剖真正的不可替代价值在路径操作子树操作只是剖分顺序顺手带来的福利。做题时先看清楚题问的是路径还是子树不要把简单问题复杂化。5.3 进阶玩法速览树剖再往上走可以跟很多数据结构叠出花来。这里列几个我实际写过的典型方向路径边权操作把每条边的权值压到它深度更深的那个子节点上这样边权路径操作就转化成了点权路径操作。这是一个非常常用的转换技巧几乎所有边权类树剖题都离不开它。路径上第 k 小配合可持久化线段树基于 dfn 序建可持久化版本查询路径时把四个版本做差再二分。这是树剖从入门走向进阶的常见一步。动态树问题树剖适合处理静态树结构上的路径问题。如果树会动态变更形态比如加边、删边那就得升级成 LCT动态树。LCT 的思想与树剖有一定传承关系把树剖理解透彻之后再接触 LCT 会轻松不少。换根操作先按某个固定根剖分然后通过分类讨论把换根后的子树转化成原树剖分下某些子树或补集的组合。这种类型在练习中偶尔出现属于树剖应用的升级版。看到这里你会发现树剖不是孤立的算法它更像一把把树切成一维区间的刻刀。切完之后用线段树还是别的数据结构去加工由题目需求和你自己的工具箱决定。这也是它生命周期特别长的原因。6. 常见的坑与调试经验6.1 写树剖最容易翻车的五个细节第一空节点的表示。我强烈建议全模板统一用 0 表示空节点。把 fa[1] 设为 0heavy[u] 初始为 0叶子节点的 heavy 也是 0。有人喜欢用 -1但如果后续代码里到处写 if (heavy[u] -1)一旦某个数组忘记初始化或者两套模板混用容易出现非常隐蔽的错误。统一用 0 会让代码更干净。第二第二遍 DFS 必须先重后轻。我见过有人图省事直接在邻接表里按输入顺序 DFS不主动优先后走重儿子。这在某些数据下看起来还能跑出正确结果但只要树形一变同链上的 dfn 连续性被破坏后面的区间操作全盘崩坏。这个问题不是碰运气能躲过去的性质没有维护住迟早出事。第三dfn 和原节点编号混淆。线段树维护的区间编号是 dfn不是原树节点编号。在 path_add 或 path_query 里写 seg.update(dfn[a], dfn[b]) 时a 和 b 都必须是剖分后的新编号。这个 bug 最典型的症状是小样例轻易通过一跑大队列数据就错得毫无规律。排查时先打印 dfn 数组和实际更新区间对比一下。第四while 循环结束后的最后一段区间不要漏。循环跑完之后a 和 b 在同一条链上它们之间仍然可能隔着一段路径这段必须单独处理。当年我复查线段树路径模板题时就曾经因为漏掉这最后一段样例全过、正式数据 WA 到怀疑人生。如果碰巧最后一次循环时 a 刚好跳到了 LCA那最后这段是空区间测不出来换一组数据立刻原形毕露。第五线段树的懒标记必须扎实。树剖本身不涉及懒标记但一旦和带 lazy 的线段树配合区间覆盖和区间加操作的 pushdown 一定要写对。这类 bug 本质上属于线段树本身的错误但树剖题普遍跑大数据会把线段树的任何小瑕疵放大得很明显。建议先单独对拍一个线段树模板确认无误后再叠加树剖逻辑否则两个模块的 bug 会互相污染排查难度成倍增长。6.2 我的调试三板斧写树剖题最怕的就是样例过了然后无限 WA。我个人的调试流程非常固定三板斧下来大部分问题都能定位出来。第一板斧打印剖分数组。在两次 DFS 结束后把 fa、depth、sz、heavy、top、dfn 全部打印出来然后对着自己画好的树手动核对。尤其要看 top 数组每个节点的链头是否符合重边连续、轻儿子另起新链的规则。这一步能快速排除剖分阶段的问题。第二板斧随机小数据对拍。写一个朴素的暴力版本直接一步一步往上爬逐点修改、逐点求和再写一个基于树剖的版本然后随机生成树和随机操作不断比对两个程序的结果。数据规模控制在 n 50操作次数几千组基本可以把所有逻辑性 bug 全部逼出来。对拍脚本只要写过一次后续几乎所有的数据结构题都能复用很值得投入时间。第三板斧单独验证 LCA。如果确认剖分没问题、线段树没问题但路径操作还是错那就先单独写一个 lca 函数和倍增法的答案暴力比对。因为 LCA 是路径操作的地基只要 LCA 错了路径操作必然跟着错而且这种错误很难直接从路径结果里逆推出来。把 LCA 先锁定为正确再把问题范围缩小到线段树操作上思路会清晰很多。6.3 递归爆栈与性能树剖的两遍 DFS 都是递归如果树被构造成一条深度很大的链递归深度可能轻松超过 10^5 甚至 10^6在一些评测环境下直接爆栈。爆栈的报错形式多种多样有时是运行时错误有时会被误判成超时非常具有欺骗性。我自己的习惯是如果题目给的数据明确可能深度很大在一开始就考虑把 DFS 改写成显式栈写法的迭代版本。这个改造本身不复杂只是把系统调用栈换成自己维护的栈数据结构但需要花一点时间调试。如果不想一开始就写迭代版可以先观察评测环境是否允许扩大栈空间有些在线平台能支持有些不行所以最稳妥的方案仍然是迭代 DFS。另外需要提一嘴的是树剖后线段树操作本身的时间复杂度是 O(log n)单次路径操作会调用 O(log n) 次线段树操作整体是 O(log^2 n)。这在绝大多数题目里都足够快。如果你对常数比较敏感可以考虑用线段树替代部分树状数组无法完成的操作但不要为了常数优化牺牲代码可读性。最后再分享一个小技巧树剖模板写熟之后你可以试着在 dfs1 里顺手记录每个节点到其链头的边数这样求路径长度时又能省掉一次 lca 调用。但这个属于针对特定题型的优化不是通用模板的一部分按需使用即可。我个人在实际写题中的体会是不要死记模板。把每次跳一整条链、链与链之间靠轻边连接、同链后取深度浅者为 LCA的图景记在心里比记住代码的每一行重要得多。调试时遇到问题回到剖分结果那张图上去对照大部分错误一眼就能看出来。树链剖分本身并不复杂它只是把树这个看似二维的结构整齐地切成了一堆适合一维数据结构管理的区间。一旦你真正掌握了这个切法后面读很多树上难题的题解都会觉得眼前豁然开朗。 
长河君 · 2026/10/21 9:29:11 · 阅读 1.2k 树链剖分最通俗讲解：原理、两次DFS与路径操作实战
树链剖分配合LCA是我在树上数据结构这条路上真正开窍的第一个里程碑。最开始翻开题解满屏的 dfn、top、heavy 直接把我看懵了。后来自己把一棵小树完整地在纸上剖了一遍才明白它根本不是多玄妙的东西——它只是非常朴素地告诉你树上的任意一条路径可以被拆成 O(log n) 段连续的区间而连续的区间线段树这类数据结构接得毫不费力。这篇文章我打算用尽量大白话的方式把剖分的原理、两次 DFS 的细节、求 LCA 的完整过程以及我这些年写题踩过的坑一次性讲透。适合有一点树和图 DFS 基础的人至少要知道树的遍历怎么写、递归是怎么回溯的。1. 树上的路径问题到底难在哪1.1 一次朴素查询的真实代价先看一个最常见的场景给一棵 n 个节点的树每个点有点权。要求支持两类操作把 a 到 b 路径上所有点的权值加一个数以及查询 a 到 b 路径上所有点的权值之和。如果第一次接触这类题绝大多数人会写暴力从 a 一步一步往上走到 LCA再从 b 一步一步往上走到 LCA一路上把经过的点全部改一遍或者统计一遍。这个做法本身没有错但它的耗时完全取决于路径长度。当树被故意构造成一条直线时a 和 b 分别取两端的节点一次操作就要遍历 n 个点。操作次数 q 一多总复杂度就是 O(nq)在 n 和 q 都在 10^5 量级的情况下跑完全部数据基本等于不可能。有人会问树上两点路径用倍增法先求 LCA 不也能 O(log n) 吗这里必须分清楚一个概念求 LCA 和修改路径上所有点是两件完全不同的事。倍增法确实能快速告诉你 LCA 是谁但当你要把 a 到 b 之间的所有点都摘出来操作时倍增法帮不上太多忙——你还是得一个点一个点地跳或者在倍增数组里额外维护信息而那样能维护的信息形态非常有限。树链剖分的价值恰恰体现在这里它不仅能求 LCA更重要的是能把一条路径切成若干段连续的区间然后把这些区间依次交给线段树处理。我平时跟人讲这个思路时经常打一个比方地图上两个地点之间的最短距离用公式立刻能算但如果要求你把路径上所有路口都装上摄像头你至少得知道这条路到底经过哪些路口、按什么顺序经过。树链剖分干的事就是给你一张路条清单写着先走这段、再走那段、最后走哪段清清楚楚。1.2 能不能把树拉直我们已经很熟悉一个工具DFS 序。给一棵有根树做深度优先遍历每个点会获得一个访问时间戳。如果题目要求修改以 u 为根的子树中所有点或者查询子树信息利用 DFS 序可以非常舒服地完成因为一棵子树里的所有点在 DFS 序上恰好对应一段连续的编号。那路径呢很遗憾任意一条路径上的点在 DFS 序里大概率是打散的。路径可能一会儿进入某棵子树一会儿又跳出来进入另一棵子树直接基于普通 DFS 序做路径操作完全行不通。不过这个失败给了我们一个重要的启发如果我能人为设计一种编号方式让任意路径都被拆成少数几段连续编号问题就迎刃而解了。树链剖分就是沿着这个思路设计出来的把整棵树拆成若干条链每条链内部的节点编号连续任意一条树上的路径等于若干个完整链段的拼接。你在一条主干道上来回走自然比在迷宫一样的巷子里摸方向快得多。2. 轻重链剖分核心概念一次看懂2.1 重儿子与重链的定义树链剖分有很多流派长链剖分、实链剖分都有各自的应用场景。竞赛和面试里最常见、也最值得先掌握的是轻重链剖分它做决策的核心依据是子树大小。对于一个节点 u假设它有若干个儿子 v1、v2、v3……我们先做一次 DFS把每个儿子的子树大小 sz[v] 都算出来。其中 sz 最大的那个儿子叫 u 的重儿子其余儿子都叫轻儿子。连接 u 与重儿子的那条边叫重边连接 u 与轻儿子的边叫轻边。把若干条连续的重边串起来就形成了一条重链。这里有一个容易忽略的点一个孤立的节点也可以视为一条长度只有 1 的链。这样规定之后整棵树会被完全拆分成若干条互不相交的重链每个节点恰好属于其中一条。还有一个细节顺带提一下如果一个节点有多个儿子的子树大小相同随便选一个当重儿子即可这不影响正确性也不会改变复杂度只是最终剖分出来的链形态可能有细微差别。不需要为了哪个更优纠结程序里只要保证同一棵树的剖分结果是确定一致的就行。为什么偏偏选 subtree size 最大的儿子直观上我们希望那些体量很大的分支尽量待在比较长的链里这样大多数节点都躺在大链上真正需要频繁换链的场景就会变少。后面你会看到正是这个选择直接决定了跳链次数的上界。2.2 轻边数量的上界复杂度自信的根源树链剖分最核心、最漂亮的性质是从根节点走到任意一个节点途经的轻边数量不超过 O(log n)。第一次看到这个结论的人往往会觉得不可思议但证明其实非常短。假设当前走到了节点 u下一步要通过一条轻边走到它的轻儿子 v。注意 v 是轻儿子说明 u 的重儿子的子树大小至少不小于 sz[v]。那么我们可以写一个非常简单的不等式设 u 的重儿子为 r则 sz[v] ≤ sz[r]。同时v 和 r 都是 u 的不同儿子它们两个的子树合起来再加上 u 自己才构成 u 的整棵子树所以 sz[r] sz[v] ≤ sz[u] - 1。把两个不等式合并得到 2 × sz[v] ≤ sz[u] - 1也就是 sz[v] sz[u] / 2。这就是关键每经过一条轻边所在的子树大小至少缩水一半。那么从根出发最多经过 floor(log2 n) 条轻边当前所在子树的规模就会缩小到 1也就是抵达叶子节点。所以根到任意节点的路径上轻边数量是 O(log n)。有了这个性质整个树剖的复杂度就有了底气任意一条从 a 到 b 的路径可以看作 a 到 LCA 再接 b 到 LCA 两段。每一段里轻边的数量都不超过 O(log n)意味着我们在处理路径时最多需要切换 O(log n) 次链。这个 log 级别的上界就是所有基于树剖做路径操作的数据结构的复杂度根基。2.3 剖分过程中需要维护哪些数组写树剖模板前最好先把下面这些数组的含义全部背熟。它们就是剖分的全部家当。数组名含义由哪一遍 DFS 得到fa[u]u 的父亲节点编号第一遍depth[u]u 的深度根深度为 1第一遍sz[u]以 u 为根的子树的节点总数第一遍heavy[u]u 的重儿子编号0 表示没有第一遍top[u]u 所在重链的链头节点第二遍dfn[u]u 剖分后获得的新编号第二遍rnk[i]新编号 i 对应的原树节点第二遍最后这个 rnk 数组经常被初学者忽略但它非常关键。因为后续线段树或者树状数组管理的区间是基于 dfn 编号的段树里存的是 dfn 序上的信息当我们需要知道线段树里第 i 个位置到底对应原树的哪个节点时就必须借助 rnk 反查回去。这一步如果漏了代码会在各种意想不到的地方爆出错。我记得早期自己写树剖题时犯过一种很典型的错误线段树明明管的是 dfn 区间我却在查询时稀里糊涂地用了原节点编号去访问线段树结果样例都能过、一到正式数据就 WA 到崩溃。这种 dfn 与原始编号混淆的问题几乎是每个顺手写过树剖的人都会经历的阶段后面的答疑部分我会专门再讲。3. 两次DFS从理论到第一行代码3.1 第一遍DFS统计家族信息第一遍 DFS 的任务是摸底把每个节点的父亲、深度、子树大小和重儿子全部统计出来。代码如下void dfs1(int u, int father) { fa[u] father; depth[u] depth[father] 1; sz[u] 1; int max_sz 0; for (int v : g[u]) { if (v father) continue; dfs1(v, u); sz[u] sz[v]; if (sz[v] max_sz) { max_sz sz[v]; heavy[u] v; } } }细节一sz[u] 初始化为 1代表节点 u 自身。DFS 回溯时把每个儿子的 sz 累加进来就得到了完整的子树大小。这个递推关系是所有后续判断的基础。细节二max_sz 初始为 0。如果 u 是叶子节点循环里一个儿子也不会进入heavy[u] 会保持为 0表示没有重儿子。我建议全模板统一用 0 表示空节点原因后面会在避坑部分展开。细节三整个第一遍 DFS 必须理解成后序处理——先递归下去把儿子的信息算完回溯时再汇总到父节点。如果你把更新 sz 和 heavy 的代码写在递归之前那 sz[v] 还是初始状态整个逻辑就全乱了。3.2 第二遍DFS分链与编号第二遍 DFS 的任务是切链把树重新组织成若干条重链同时给每个节点分配一个新的编号 dfn。这一段是整个剖分里最需要仔细理解的部分。void dfs2(int u, int t) { top[u] t; dfn[u] timer; rnk[timer] u; if (heavy[u] 0) return; // 叶子节点直接结束 dfs2(heavy[u], t); // 优先走重儿子保持同链编号连续 for (int v : g[u]) { if (v fa[u]) continue; if (v heavy[u]) continue; dfs2(v, v); // 轻儿子作为新链的链头 } }关键在倒数第三行的先走重儿子。为什么这条顺序如此重要因为我们要保证同一条重链上的节点dfn 编号是连续的。只有先递归重儿子把整条重链一口气排完这条链上的节点才会在编号上形成一整段。你可以想象整理书架你希望同一套丛书的所有册数挨在一起那就要先把这一套书完整地摆好再去摆下一套。如果摆完一本就插一本别的书同一套丛书就被打散了。树剖同理同一条链的节点编号如果不连续后面线段树按区间操作时就会破坏整段区间。处理完重儿子之后再依次处理轻儿子。每个轻儿子都以自己作为新链的链头所以传入 dfs2(v, v)。至于整棵树的第一个调用直接写 dfs2(1, 1)根节点就是第一条重链的链头。3.3 用手推一个小树把剖分看一遍光看代码容易虚空我们拿一棵只有 7 个节点的树手动完整地剖一遍。树的形态如下根节点是 1它有儿子 2 和 3节点 2 有儿子 4 和 5节点 3 有儿子 6节点 5 有儿子 7先跑第一遍 DFS。我们按输入顺序假设进入 1 后先访问 2。7 是叶子sz[7]15 的子树包含自己和 7所以 sz[5]24 是叶子sz[4]1。那么节点 2 的两个儿子子树大小分别是 1 和 2其中更大的是 5因此 heavy[2]5。节点 3 那边6 是叶子sz[6]13 唯一的儿子就是重儿子所以 heavy[3]6。最后看根节点 1儿子 2 的子树大小为 3包含 2、4、5、7儿子 3 的子树大小为 2包含 3、6所以 heavy[1]2。第二遍 DFS 从 dfs2(1, 1) 开始。访问 1dfn[1]1top[1]1。接着优先走重儿子 2dfn[2]2top[2]1。2 的重儿子是 5继续走dfn[5]3top[5]1。5 的重儿子是 7继续走dfn[7]4top[7]1。此时整条链 1-2-5-7 排完了编号是 1、2、3、4。回到节点 2处理轻儿子 4dfn[4]5top[4]4这条链只有它一个节点。再回到根节点 1处理轻儿子 3dfn[3]6top[3]3。3 还有重儿子 6继续走dfn[6]7top[6]3链 3-6 排完了。最终剖分结果非常清晰链 11-2-5-7链头 1编号 1, 2, 3, 4链 24链头 4编号 5链 33-6链头 3编号 6, 7你可以观察到一个现象每条链上的编号都是连续的这就是第二遍 DFS 中先重后轻策略的功劳。同时还有一个额外的福利任意一个节点的子树在 dfn 序上依然是连续区间。比如节点 2 的子树包含 2、4、5、7对应编号 2、3、4、5正好是区间 [2,5]。这个性质在后面的子树操作里会直接用到。4. 树链剖分求LCA跳跃的艺术4.1 为什么剖分之后LCA变得这么容易树链剖分完成之后求两个点的 LCA 从一步一步往上爬升级成了一条链一条链地跳。先考虑最简单的情形如果 a 和 b 已经在同一条重链上那它们之间的祖先关系是确定的深度更小的那个就是 LCA。在同一链上的两点之间是一段连续的祖先-后代关系取深度较小的那个自然没问题。如果 a 和 b 不在同一条链上呢此时让它们跳链。具体来说比较 top[a] 和 top[b] 的深度谁的链头更深就说明谁离 LCA 更远那就把整个链头所在的链条跳过去——直接把那个节点改成链头的父亲 fa[top[x]]。然后重复这个比较直到两个点落到同一条链上。为什么每次跳一整条链是安全的因为 LCA 不可能藏在这种被整条跳过的深层链上。如果 a 所在链的链头 top[a] 深度比 top[b] 更深那 a 和 b 的 LCA 一定还在 top[a] 的上方这个链头以及它下方的整条链都不可能同时包含 b 那边的路径所以 a 可以直接跳到链头的父亲不会跳过 LCA。这个过程跟手动求 LCA 时的直觉一致谁位置更深谁往上走。只不过树剖把走一步升级成了走一整条链。每次跳链本质上都会跨过至少一条轻边前面我们已经证明过从任意点出发到祖先的路径上轻边总数是 O(log n)所以整个 while 循环的次数也稳定在 O(log n)效率有足够保障。4.2 代码实现与手推样例直接上代码非常短int lca(int a, int b) { while (top[a] ! top[b]) { if (depth[top[a]] depth[top[b]]) { swap(a, b); } a fa[top[a]]; } return depth[a] depth[b] ? a : b; }不少初学者看到这个 while 循环能理解但看到最后那个 return 又会愣一下为什么跳出循环了还要比一次深度原因是 while 循环结束时a 和 b 已经位于同一条重链上了。既然在一条链上它们必然是一上一下的祖先关系深度小的那个就是 LCA。直接比较两个点的深度返回较浅的那个即可。我们用第 3 章那棵树手动跑一遍 lca(7, 6)。初始 a7b6。top[7]1top[6]3不相等。 比较 depth[top[a]]depth[1]1 和 depth[top[b]]depth[3]2前者更浅于是交换当前 a6b7。 执行 afa[top[6]]fa[3]1。现在 a1b7。top[1]1top[7]1相等跳出循环。 比较 depth[1]1 和 depth[7]4返回 1。LCA 是 1正确。再试一组 lca(4, 7)。初始 a4b7。top[4]4top[7]1不相等。 比较 depth[4]2 和 depth[1]1前者更大不交换直接 afa[top[4]]fa[4]2。 现在 a2b7top[2]1top[7]1相等跳出循环。 比较 depth[2]2 和 depth[7]4返回 2。LCA 是 2正确。强烈建议你多选几组点在纸上把每一步的 a、b、top、depth 全部写下来。我第一次完整跳明白这个流程之后后面的路径操作基本就是照葫芦画瓢了。4.3 和常见LCA方法放在一起比一比可能有人会问我本来就会倍增法求 LCA为什么还要学树剖实际上这两个方法是不同场景下的不同工具。我把主流的 LCA 解法拉到一个表里对比这样差异一眼就能看清方法预处理复杂度单次查询能否维护路径信息倍增法O(n log n)O(log n)较难能维护的信息很有限Tarjan 离线O(n q)需离线处理无法在线修改树链剖分O(n)O(log n)可以直接配合线段树做区间操作RMQ 欧拉序O(n log n)O(1)无法直接维护路径修改看出区别了吗树链剖分的预处理甚至比倍增还便宜只需要 O(n) 的时间就能完成两遍 DFS查询也有 O(log n) 的单次复杂度。更重要的是它天然给出了路径对应的链段拆分方案这才是做路径修改和路径查询的核心能力。如果你只是单纯求 LCA不涉及任何修改操作那我承认倍增法甚至 RMQ 都更省事但一旦题目要求改路径上的点权或查路径上最大值/和树链剖分几乎是绕不开的正解。竞赛中树链剖分 线段树是一整套非常成熟的组合技学会树剖求 LCA 只是第一步往上一小步就是路径操作性价比非常高。5. 不只是LCA树剖的威力在路径操作5.1 路径加、路径求和先拆成O(log n)个区间树链剖分最经典的落地应用是支持路径上所有点权值加一个数以及查询路径上所有点权值之和。思路跟求 LCA 几乎一致每次进入 while 循环把当前这条链上的那一段区间交给线段树做一次区间修改或区间查询然后把节点跳到链头的父亲。唯一需要额外小心的是最后 a 和 b 落到同一条链上时要把深度小的那个放在区间左端因为线段树的区间操作要求左端点编号小于右端点。void path_add(int a, int b, int val) { while (top[a] ! top[b]) { if (depth[top[a]] depth[top[b]]) { swap(a, b); } seg.update(dfn[top[a]], dfn[a], val); a fa[top[a]]; } if (depth[a] depth[b]) { swap(a, b); } seg.update(dfn[a], dfn[b], val); } int path_query(int a, int b) { int res 0; while (top[a] ! top[b]) { if (depth[top[a]] depth[top[b]]) { swap(a, b); } res seg.query(dfn[top[a]], dfn[a]); a fa[top[a]]; } if (depth[a] depth[b]) { swap(a, b); } res seg.query(dfn[a], dfn[b]); return res; }对比一下第 4 章的 LCA 代码你会发现结构几乎是一个模子刻出来的区别只有两点一是对 dfn 区间额外执行了线段树操作二是最后同链时处理最后一段区间。这里有一个关于方向和顺序的提醒路径本身是 a 到 LCA 再到 b 的折线但我们在拆区间时并不关心每一段的方向因为普通权值加和的运算具有交换律。不过如果你要维护的信息是有方向性的比如边权差、颜色段数量、区间翻转等那就必须仔细考虑区间合并的顺序了。这类有向信息的维护难度会高出不少建议初学时先把无方向的路径和彻底吃透再往深走。5.2 子树操作剖分留下的彩蛋你在第 3 章手推剖分时应该已经注意到在 dfn 编号方式下一棵子树在树上的所有节点其编号是连续的。这时候修改以 u 为根的子树上所有点权就变成了一次简单的线段树区间操作。void subtree_add(int u, int val) { seg.update(dfn[u], dfn[u] sz[u] - 1, val); }一行代码就能搞定子树修改。这也让树剖 线段树的组合拥有两套能力路径操作走跳链 区间操作子树操作直接走区间操作。真正做难题时这两种操作往往会在同一道题里同时出现非常常见。顺带说一句如果你只做子树相关的问题普通 DFS 序就能满足没必要动用树剖。树剖真正的不可替代价值在路径操作子树操作只是剖分顺序顺手带来的福利。做题时先看清楚题问的是路径还是子树不要把简单问题复杂化。5.3 进阶玩法速览树剖再往上走可以跟很多数据结构叠出花来。这里列几个我实际写过的典型方向路径边权操作把每条边的权值压到它深度更深的那个子节点上这样边权路径操作就转化成了点权路径操作。这是一个非常常用的转换技巧几乎所有边权类树剖题都离不开它。路径上第 k 小配合可持久化线段树基于 dfn 序建可持久化版本查询路径时把四个版本做差再二分。这是树剖从入门走向进阶的常见一步。动态树问题树剖适合处理静态树结构上的路径问题。如果树会动态变更形态比如加边、删边那就得升级成 LCT动态树。LCT 的思想与树剖有一定传承关系把树剖理解透彻之后再接触 LCT 会轻松不少。换根操作先按某个固定根剖分然后通过分类讨论把换根后的子树转化成原树剖分下某些子树或补集的组合。这种类型在练习中偶尔出现属于树剖应用的升级版。看到这里你会发现树剖不是孤立的算法它更像一把把树切成一维区间的刻刀。切完之后用线段树还是别的数据结构去加工由题目需求和你自己的工具箱决定。这也是它生命周期特别长的原因。6. 常见的坑与调试经验6.1 写树剖最容易翻车的五个细节第一空节点的表示。我强烈建议全模板统一用 0 表示空节点。把 fa[1] 设为 0heavy[u] 初始为 0叶子节点的 heavy 也是 0。有人喜欢用 -1但如果后续代码里到处写 if (heavy[u] -1)一旦某个数组忘记初始化或者两套模板混用容易出现非常隐蔽的错误。统一用 0 会让代码更干净。第二第二遍 DFS 必须先重后轻。我见过有人图省事直接在邻接表里按输入顺序 DFS不主动优先后走重儿子。这在某些数据下看起来还能跑出正确结果但只要树形一变同链上的 dfn 连续性被破坏后面的区间操作全盘崩坏。这个问题不是碰运气能躲过去的性质没有维护住迟早出事。第三dfn 和原节点编号混淆。线段树维护的区间编号是 dfn不是原树节点编号。在 path_add 或 path_query 里写 seg.update(dfn[a], dfn[b]) 时a 和 b 都必须是剖分后的新编号。这个 bug 最典型的症状是小样例轻易通过一跑大队列数据就错得毫无规律。排查时先打印 dfn 数组和实际更新区间对比一下。第四while 循环结束后的最后一段区间不要漏。循环跑完之后a 和 b 在同一条链上它们之间仍然可能隔着一段路径这段必须单独处理。当年我复查线段树路径模板题时就曾经因为漏掉这最后一段样例全过、正式数据 WA 到怀疑人生。如果碰巧最后一次循环时 a 刚好跳到了 LCA那最后这段是空区间测不出来换一组数据立刻原形毕露。第五线段树的懒标记必须扎实。树剖本身不涉及懒标记但一旦和带 lazy 的线段树配合区间覆盖和区间加操作的 pushdown 一定要写对。这类 bug 本质上属于线段树本身的错误但树剖题普遍跑大数据会把线段树的任何小瑕疵放大得很明显。建议先单独对拍一个线段树模板确认无误后再叠加树剖逻辑否则两个模块的 bug 会互相污染排查难度成倍增长。6.2 我的调试三板斧写树剖题最怕的就是样例过了然后无限 WA。我个人的调试流程非常固定三板斧下来大部分问题都能定位出来。第一板斧打印剖分数组。在两次 DFS 结束后把 fa、depth、sz、heavy、top、dfn 全部打印出来然后对着自己画好的树手动核对。尤其要看 top 数组每个节点的链头是否符合重边连续、轻儿子另起新链的规则。这一步能快速排除剖分阶段的问题。第二板斧随机小数据对拍。写一个朴素的暴力版本直接一步一步往上爬逐点修改、逐点求和再写一个基于树剖的版本然后随机生成树和随机操作不断比对两个程序的结果。数据规模控制在 n 50操作次数几千组基本可以把所有逻辑性 bug 全部逼出来。对拍脚本只要写过一次后续几乎所有的数据结构题都能复用很值得投入时间。第三板斧单独验证 LCA。如果确认剖分没问题、线段树没问题但路径操作还是错那就先单独写一个 lca 函数和倍增法的答案暴力比对。因为 LCA 是路径操作的地基只要 LCA 错了路径操作必然跟着错而且这种错误很难直接从路径结果里逆推出来。把 LCA 先锁定为正确再把问题范围缩小到线段树操作上思路会清晰很多。6.3 递归爆栈与性能树剖的两遍 DFS 都是递归如果树被构造成一条深度很大的链递归深度可能轻松超过 10^5 甚至 10^6在一些评测环境下直接爆栈。爆栈的报错形式多种多样有时是运行时错误有时会被误判成超时非常具有欺骗性。我自己的习惯是如果题目给的数据明确可能深度很大在一开始就考虑把 DFS 改写成显式栈写法的迭代版本。这个改造本身不复杂只是把系统调用栈换成自己维护的栈数据结构但需要花一点时间调试。如果不想一开始就写迭代版可以先观察评测环境是否允许扩大栈空间有些在线平台能支持有些不行所以最稳妥的方案仍然是迭代 DFS。另外需要提一嘴的是树剖后线段树操作本身的时间复杂度是 O(log n)单次路径操作会调用 O(log n) 次线段树操作整体是 O(log^2 n)。这在绝大多数题目里都足够快。如果你对常数比较敏感可以考虑用线段树替代部分树状数组无法完成的操作但不要为了常数优化牺牲代码可读性。最后再分享一个小技巧树剖模板写熟之后你可以试着在 dfs1 里顺手记录每个节点到其链头的边数这样求路径长度时又能省掉一次 lca 调用。但这个属于针对特定题型的优化不是通用模板的一部分按需使用即可。我个人在实际写题中的体会是不要死记模板。把每次跳一整条链、链与链之间靠轻边连接、同链后取深度浅者为 LCA的图景记在心里比记住代码的每一行重要得多。调试时遇到问题回到剖分结果那张图上去对照大部分错误一眼就能看出来。树链剖分本身并不复杂它只是把树这个看似二维的结构整齐地切成了一堆适合一维数据结构管理的区间。一旦你真正掌握了这个切法后面读很多树上难题的题解都会觉得眼前豁然开朗。