写“LCA下”之前先交代一下上篇到了哪里最常见的倍增法已经讲完朴素跳父节点也提过一嘴。那为什么还需要再写一篇因为实战里你会很快发现倍增并不是万能的——它查询是 O(log n)但预处理要 O(n log n)它在线但不能处理“一次给你一堆查询然后让你批量回答”的最优场景它对树上路径统计类问题往往只是垫脚石不是终点。这篇下篇我把欧拉序RMQ、Tarjan离线、树链剖分这三条主流路线全部过一遍再讲清楚 LCA 在树上差分、路径最值、虚树这些进阶场景里是怎么当“基建”用的。文章照旧按我自己的代码习惯写C 为主思路部分尽量不依赖语言。1. 欧拉序 RMQ把树压平LCA 就变成区间最值倍增法是在树上原地跳而欧拉序RMQ 的思路完全相反我不在树上玩了我把整棵树按 DFS 访问顺序展开成一个序列然后用 ST 表预处理这个序列最后每次查询就是查一段区间里深度最小的点。第一次看到这个思路的人通常会觉得绕但它其实是“把树上问题变成序列问题”这个通用套路的最佳入门案例。1.1 欧拉序到底和 DFS 序有什么不同很多初学者会把欧拉序和 DFS 序搞混。DFS 序是每个节点进入时记录一次所以序列长度恰好是 n欧拉序是“每经过一个点就记录一次”包括从子节点回溯回父节点时也要再记一次父节点。也就是说欧拉序的长度是 2n-1每条边会被经过两次其中每个节点会出现多次第一次出现的位置记为 first[u]深度记为 dep[u]。举一棵最简单的树当例子根是 11 有两个孩子 2 和 32 有孩子 4。DFS 从 1 出发欧拉序大概长这样1, 2, 4, 2, 1, 3, 1每个节点第一次出现的位置分别是first[1]0first[2]1first[3]5first[4]2。这序列有个关键性质对于任意两个节点 u 和 v从 first[u] 一路走到 first[v] 这段区间里的深度最小值节点正好就是 lca(u, v)。比如查 4 和 3区间是 first[4]2 到 first[3]5序列段是 [4, 2, 1, 3]深度分别是 2、1、0、1最小的是 1而 1 恰好就是 LCA。这个性质成立的原因很好理解u 到 v 的路径在 DFS 过程中必然经过它们的最近公共祖先而这段区间里不可能出现比 LCA 深度更浅的节点否则那个更浅的节点就应该是它们的公共祖先矛盾。1.2 把区间最值转成 RMQ既然查询变成了“找区间深度最小的节点”思路就清晰了用 ST 表预处理欧拉序中每个位置出发、长度为 2^k 的区间里深度最小的节点查询时把区间 [l, r] 拆成两个可重叠区间取 min。RMQ 问题要求的重叠不影响最值所以 ST 表这种稀疏表非常合适。代码实现如下const int MAXN 100005; const int LOGN 20; vectorint g[MAXN]; int euler[MAXN * 2], dep[MAXN], first[MAXN]; int st[MAXN * 2][LOGN]; // st[i][j] 表示从 i 开始长 2^j 的区间里深度最小的节点编号 int tot; // 欧拉序长度 void dfs(int u, int fa, int d) { dep[u] d; first[u] tot; euler[tot] u; for (int v : g[u]) { if (v fa) continue; dfs(v, u, d 1); euler[tot] u; // 回溯时记录父节点 } } void buildST() { for (int i 0; i tot; i) st[i][0] euler[i]; for (int j 1; (1 j) tot; j) { for (int i 0; i (1 j) - 1 tot; i) { int a st[i][j - 1]; int b st[i (1 (j - 1))][j - 1]; st[i][j] (dep[a] dep[b]) ? a : b; } } } int lca(int u, int v) { int l first[u], r first[v]; if (l r) swap(l, r); int k 31 - __builtin_clz(r - l 1); int a st[l][k], b st[r - (1 k) 1][k]; return (dep[a] dep[b]) ? a : b; }这里有个容易被忽略的细节预处理 ST 表之前一定要先 dfs() 把所有节点的 first 和 euler 填好而且目标树如果不是从 1 开始要记住进入 dfs 时的根节点参数。__builtin_clz是 GCC 内置函数用来快速算二进制前导零个数等价于算 log2。1.3 在线查询的极致预处理 O(n log n)查询 O(1)这套方案的时间复杂度很好DFS 一次 O(n)ST 表预处理 O(n log n)每次查询 O(1)。相比倍增法的 O(log n) 查询在查询量极大的场景下优势明显。空间上欧拉序是 2n-1ST 表要开2n * log(2n)的二维数组大的时候比较吃内存尤其 n 到 2e5 时差不多要 2e5 * 18 * 4 字节约 14MB还能接受。我实际写题时遇到“查询次数达到 n 的两三倍级别”的题目会优先考虑这个方案因为 O(1) 查询在常数上确实比倍增友好。不过要注意ST 表在初始化时需要比较 dep[a] 和 dep[b]如果两棵子树深度相同随意选哪个都不影响正确性因为两者都在区间内且它们的 LCA 深度更小。这个“取其一”的操作不会引起错误。2. Tarjan 离线算法一次 DFS 顺手回答所有问题欧拉序RMQ 虽然查询快但它还是在线算法需要把所有信息预处理完才能回答。如果题目把查询全部给出来了而且允许离线处理那 Tarjan 算法会是代码量最小、常数最小的方案甚至比 ST 表还好写。2.1 “离线”到底意味着什么离线指的是算法可以预先看到所有查询然后统一安排处理顺序在线则必须按查询给出的顺序一个一个回答。Tarjan 算法属于离线算法它把所有查询挂在树上只跑一次 DFS在递归的过程中顺带把所有答案填完。这个算法的核心观察是DFS 在回溯时如果某个节点 u 的所有子树都已经访问完那么 u 和它的兄弟子树中任意已访问节点的 LCA 一定可以追溯到 u 的祖先链上。为了高效维护“当前已经回溯到哪一层”算法用并查集跟踪每个节点的“当前祖先代表”。2.2 并查集在算法里的真正角色Tarjan 算法的框架是用一个vis[u]数组标记节点是否已访问。用一个anc[u]数组记录节点 u 所属集合的“代表”这个代表通常是当前 DFS 栈中某层节点。DFS 进入节点 u 时先令anc[u] u然后递归访问它的每个孩子。孩子 v 递归结束后执行merge(u, v)也就是把 v 所在集合合并到 u 所在集合并让集合的代表保持为 u。标记vis[u] true。遍历所有挂在 u 上的查询(u, v)如果vis[v] true那么lca find(v)。为什么find(v)就是答案这需要仔细想v 已经访问过说明 v 在 u 的某个兄弟子树里或者在上层节点回溯过的子树里。此时 v 所在并查集代表正是当前 DFS 栈中那个“已经回到某个祖先、且尚未离开”的节点这个祖先就是 u 和 v 的最近公共祖先。如果 v 就在 u 的子树里vis[v]不一定为 true因为 u 还没标记为访问只有 u 的全部子树处理完才会标记这时如果 v 是 u 祖先那也不会触发所以不会误判。2.3 完整可运行模板这里给出我用链式前向星存图的方式查询也用链式前向星存双向边方便统一处理。#include bits/stdc.h using namespace std; const int MAXN 500005; struct Edge { int to, next; } e[MAXN * 2], q[MAXN * 2]; int headE[MAXN], headQ[MAXN]; int cntE 0, cntQ 0; int fa[MAXN], ans[MAXN]; bool vis[MAXN]; int n, m; void addEdge(int u, int v) { e[cntE] {v, headE[u]}; headE[u] cntE; } void addQuery(int u, int v) { q[cntQ] {v, headQ[u]}; headQ[u] cntQ; } int find(int x) { return fa[x] x ? x : fa[x] find(fa[x]); } void tarjan(int u, int parent) { fa[u] u; for (int i headE[u]; i; i e[i].next) { int v e[i].to; if (v parent) continue; tarjan(v, u); fa[v] u; // 合并子节点到当前节点 } vis[u] true; for (int i headQ[u]; i; i q[i].next) { int v q[i].to; if (vis[v]) { ans[(i 1) / 2] find(v); // 这里需要能对应到查询编号 } } }上面的代码里我把查询边也存成双向链式前向星所以每一条查询实际上占了两个槽位2k-1和2k用(i1)/2可以还原出查询编号。如果你用 vector of pairs 存查询会更直观vectorpairint,int queries[MAXN]; // queries[u] {v, id} ... for (auto p : queries[u]) { int v p.first, id p.second; if (vis[v]) ans[id] find(v); }2.4 常被忽略的两个边界Tarjan 的坑比倍增少但也不是没有。第一个坑是递归深度。n 到 1e6 时DFS 递归很容易爆系统栈这时候要么手动扩栈要么换用非递归写法。我实测过大多数 OJ 默认栈够跑到 2e5 左右再往上就建议#pragma comment(linker, /STACK:102400000,102400000)或者把 DFS 改成栈模拟。第二个坑是vis[u]的标记时机。必须等所有孩子递归结束、u 自己也被“完成后”才标记如果一进函数就标记vis[u] true那查询另一端点还在子树里没访问完时会拿到一个错误的 LCA。这个顺序我见过很多新手写错排查起来很痛苦因为答案不是稳定错而是部分错。3. 树链剖分LCA 只是重链操作送你的赠品树链剖分Heavy-Light Decomposition, HLD本身不是为了求 LCA 而设计的它的目标是“把树上路径操作转化为区间操作”。但因为它天然维护了每个节点到根的跳链结构顺手求 LCA 也非常高效而且这一层功夫在后面处理链上查询时早晚要练。3.1 重链剖分的核心数组重链剖分要做两遍 DFS。第一遍求出每个节点的子树大小sz[u]、深度dep[u]、父亲father[u]和重儿子son[u]其中重儿子的定义是子树大小最大的那个孩子。第二遍按照“优先走重儿子”的顺序分配 dfs 序dfn[u]并记录每个节点所在的链顶top[u]。这些数组里LCA 最关心的是top[u]。原理很简单如果两个节点的top相同说明它们在同一条重链上深度浅的那个就是 LCA如果top不同就把top深度较深的那个节点整体跳到它top的父节点然后继续比较。3.2 跳链版 LCA 代码int lca(int u, int v) { while (top[u] ! top[v]) { if (dep[top[u]] dep[top[v]]) swap(u, v); u father[top[u]]; } return dep[u] dep[v] ? u : v; }这段代码只有几行但背后信息量很大。每次循环都把当前链顶更深的节点往上一整条链地跳跳的次数等于 u 和 v 之间经过的轻边数量加 1。轻边数量是 O(log n) 级别的因为每跳一次子树大小至少翻一倍所以总复杂度 O(log n)。3.3 第一遍和第二遍 DFS 的完整写法这里给一个我常用的完整模板int sz[MAXN], dep[MAXN], father[MAXN], son[MAXN], top[MAXN], dfn[MAXN], rnk[MAXN]; int dfsClock 0; void dfs1(int u, int fa) { sz[u] 1; father[u] fa; dep[u] dep[fa] 1; son[u] 0; int maxSize 0; for (int v : g[u]) { if (v fa) continue; dfs1(v, u); sz[u] sz[v]; if (sz[v] maxSize) { maxSize sz[v]; son[u] v; } } } void dfs2(int u, int tp) { top[u] tp; dfn[u] dfsClock; rnk[dfsClock] u; if (son[u]) dfs2(son[u], tp); // 先走重儿子保持链上 dfs 序连续 for (int v : g[u]) { if (v father[u] || v son[u]) continue; dfs2(v, v); // 轻儿子自成一条链 } }注意 dfs2 的顺序必须先递归重儿子再递归轻儿子。只有这样同一条重链上的节点才会在 dfs 序上连续分布这是后面把路径拆成若干个区间操作的基础。如果先走轻儿子重链上的 dfn 就不连续了很多带数据结构优化的操作会失效。3.4 为什么说剖分是“为路径而生”的单纯求 LCA树链剖分和倍增差不太多但剖分真正的价值在于它可以配合线段树或树状数组完成路径上的区间更新、区间查询。比如“把 u 到 v 路径上所有点的权值加上 x”“查询 u 到 v 路径上的最大值”这些操作用倍增只能干瞪眼用剖分却可以拆成 O(log n) 个区间操作然后在线段树上跑。所以我的建议是如果一道题只让你求 LCA用倍增或欧拉序RMQ 足够了如果题目里还有“路径修改/路径查询”的需求直接上树链剖分因为它的 LCA 是顺带算出来的你再换别的方案反而多写一套框架。4. 从“找祖先”到“路径问题”LCA 的高频应用场景说句实在话LCA 在真正的竞赛和工程里几乎从来不作为题目的最终目标。它永远是一个“工具”。你需要掌握的是怎么把这个工具焊进更大的框架里。4.1 树上两点距离与路径相关计算最经典的公式是设dis(u,v)表示树上 u 到 v 的路径长度边权为 1 时则有dis(u, v) dep[u] dep[v] - 2 * dep[lca(u, v)]这个公式虽然简单但很多树上问题最后都会落到它身上比如“判断一个点在路径上”也可以用它来判断点 x 在路径 u-v 上当且仅当dis(u, x) dis(x, v) dis(u, v)这个等价关系在后面虚树和动态规划题里经常出现值得记牢。如果边有权重把 dep 改成从根到该点的前缀权值和即可公式形式不变。这是 LCA 最“日常”的用法。4.2 树上差分把区间加减搬到树上的关键树上差分的思路和普通数组差分一模一样想给路径 u-v 上所有点加 1可以先在 cnt[u]cnt[v]然后 cnt[lca]--cnt[father[lca]]--。DFS 一遍从叶子累加回根最后 cnt[x] 就表示 x 被多少条路径覆盖。这是经典应用。如果是给路径 u-v 上所有边加 1公式变成cnt[u], cnt[v], cnt[lca] - 2因为边权通常会“下沉”到子节点lca 本身不参与边的统计所以减两次而不是减一次。我当年学这块时一直搞不清到底该减一次还是减两次后来自己画了棵树才彻底明白。给一个记忆技巧点权的时候lca 也要被覆盖所以要在 cnt[lca]-- 保留一次覆盖再在 father[lca]-- 一消除祖先方向的扩散边权的时候lca 上方那条边不属于路径所以直接 cnt[lca] - 2。4.3 树上 k 级祖先倍增表不止能查 LCA倍增法预处理出来的up[u][j]表除了能求 LCA还能直接求任意节点往上跳 k 步的祖先。写法就是按 k 的二进制位拆位int kthAncestor(int u, int k) { for (int j 0; j LOGN; j) { if (k (1 j)) u up[u][j]; } return u; }这个功能在“求路径中间点”“判断路径长度奇偶性”等问题里很常用。还有一个变体是长链剖分求 k 级祖先可以做到 O(1)但复杂度和代码量都高不少日常不划算有需要再说。4.4 虚树LCA 当粘合剂虚树解决的问题是树上有很多关键点但 n 很大关键点很少如果每次都跑整个树复杂度无法接受。比如一共有 1e5 个节点但某次查询只涉及 3 个关键点你显然不想跑整棵树。虚树的做法是把关键点按 dfs 序排序然后依次将相邻两个关键点的 LCA 加入候选集合最后再按 dfs 序建一棵“只包含关键点和它们 LCA”的小树。这里面 LCA 是绝对的灵魂。没有 LCA关键点之间的祖先关系完全无法压缩。构建虚树的单调栈算法核心步骤是将关键点按 dfn 排序。维护一个栈栈中元素从底到顶是当前节点到根的路径上需要保留的节点。每加入一个新点 u取栈顶元素 p stk.back()计算 l lca(u, p)。如果 l p说明 u 在 p 的子树内直接把 u 入栈。如果 l ! p说明 u 不在 p 的子树内此时不断弹栈直到栈顶深度小于等于 l 的深度然后补上 l 作为新节点并把弹出去的节点的父指针指向 l。这个过程非常容易写错我建议手跑几组例子再上考场。不过它的核心依赖就是 LCA 查询函数所以只要 LCA 写得稳虚树就成功了一半。4.5 路径最大/最小边权查询另一种常见套路是把倍增表中的up[u][j]扩展为mx[u][j]表示从 u 向上跳 2^j 步的路径上边权的最大值。查询 u-v 路径最大边权时先求 lca然后分别从 u 和 v 向上倍增到 lca 以下沿途合并 mx 值。这个技巧在最小生成树相关题目例如次小生成树里几乎是必考的LCA 又一次作为核心工具出现。5. 四套方案怎么选一份带数值的决策指南我知道看到这里很多人会问学了四种方法考试到底用哪个这里我给一个自己实践的选型表顺便把最容易坑人的几个点也一并列出来。5.1 复杂度对比总览方案预处理单次查询是否在线适用场景朴素跳父节点O(n)O(n)在线几乎不用倍增法O(n log n)O(log n)在线通用万金油代码简单欧拉序RMQO(n log n)O(1)在线查询量极大Tarjan 离线O(n m α(n))离线 O(1) 均摊离线一次性给完所有查询树链剖分O(n)O(log n)在线需要配合路径修改/查询这里的“在线”指的是能否按输入顺序立即回答查询。多数题没有强制在线但如果你写的是交互题就只能用在线方案。查询次数大于 1e6 且 n 在 2e5 以内优先欧拉序RMQ查询常数最小。查询次数一般和 n 同数量级倍增法最省心代码量最小。所有查询提前给定n 和 m 都很大Tarjan 离线常数小而且省内存。题目还要做路径加、路径和、子树覆盖等操作无脑树链剖分它求 LCA 只是副产品。5.2 翻车点与注意事项我在不同平台用这几种算法写过不少题踩过的坑可以列一长串这里挑几个最典型的。倍增表的边界up[u][j]在 j 超过 log 深度时需要是 0否则求 LCA 循环会访问到随机地址。建表时要把数组清成 0并且保证根节点的 father 是 0。欧拉序的长度很多写着写着数组只开了 n实际要 2n-1一跑边界就崩。建议直接开2 * MAXN别省那一个位置。Tarjan 的根节点标记递归进入根节点时记得也要执行vis[root] true否则挂在根节点上的查询会漏答。树链剖分 dfs2 的重儿子优先级必须把重儿子放在最前面递归否则 dfn 不连续后续所有区间操作都会出错。这个顺序问题不像逻辑错误而是一种“玄学 bug”数据一多就 WA还特别难定位。递归爆栈树如果是链状递归 DFS 深度会达到 n。n 到 5e5 时系统栈很容易溢出。比较省事的办法是写一个手写栈模拟或者用欧拉序RMQ 的方案替代递归 DFS。我自己在 n 很大时更倾向用 C 的std::function递归前先设置好ios::sync_with_stdio(false)同时尽量缩递归深度。5.3 一个个人习惯我自己的习惯是比赛时优先写倍增因为它代码短、调试快但如果题目明确说查询次数会很大我绝不犹豫直接写欧拉序RMQ。平时练习刷题时树链剖分的 LCA 我至少每隔一段时间就默写一遍因为这个代码虽然逻辑不复杂一旦不熟就会在细节上卡很久。Tarjan 离线我反而用得少但它让我理解了“离线处理”的威力这个思想在很多高级数据结构题里都会反复出现。最后再分享一个小技巧如果一道题的数据范围不允许递归 DFS又必须用树链剖分可以先把 DFS 改成显式栈的后序遍历但这样代码会变长很多。我的妥协方案是能用递归就用递归遇到明显链状的毒瘤数据就先测一下递归深度深度超过阈值就换欧拉序RMQ不跟栈空间硬刚。做算法题思路清晰永远比秀操作重要。