1. 从一次线上故障说起为什么LCA值得你花时间搞懂去年帮一个朋友排查他们内部工具的一个性能问题场景很典型一个组织架构树大概三万多节点每次要计算两个员工在组织树里的最近共同上级。他们最初的实现是暴力往上爬——把A的所有祖先塞进一个集合然后B从自己开始往上走遇到的第一个在集合里的节点就是答案。单次查询看着不慢几十毫秒但架不住前端一个页面要批量算几百对页面直接卡到转圈。这个问题的本质就是LCALowest Common Ancestor最近公共祖先。听起来像是算法竞赛里的东西但只要你处理过任何树形结构——组织架构、文件目录、DOM节点、分类体系、依赖关系图——你迟早会撞上它。而且一旦数据量上去暴力解法就会原形毕露。这篇内容我打算把LCA这件事从头到尾讲透。不是那种背个倍增模板就完事的讲法而是把为什么会有多种解法、每种解法到底在权衡什么、什么场景该选哪个、写的时候哪里最容易翻车这些真正影响你落地的东西说清楚。适合已经会写基础树遍历、但一遇到树上路径查询就发怵的开发者也适合想系统梳理一遍这块知识的老手。看完你应该能做到拿到一个问题先判断它是不是LCA再根据数据规模和查询次数直接选出合适的方案而不是无脑套模板。2. LCA到底在解决什么问题把共同祖先翻译成人话2.1 用家族树理解最近公共祖先先把这个概念用最朴素的方式说清楚。想象一棵家族树根节点是最老的祖先往下每一层是下一代。现在给你两个人问他俩血缘关系最近的那个共同长辈是谁注意最近两个字是关键。往上数所有共同的长辈都算公共祖先但我们要的是**深度最大离他俩最近**的那一个。比如你和你堂哥你们的爷爷是LCA但曾祖父也是共同祖先只不过曾祖父更远不是最近的。形式化一点给定一棵有根树对于节点u和vLCA(u, v)是同时满足是u的祖先且是v的祖先的节点中深度最大的那个。这里祖先通常包含节点自己——也就是说如果u本身就是v的祖先那LCA就是u。这个约定很重要很多实现细节都跟它有关。2.2 为什么暴力爬树会崩复杂度账要算清楚最直觉的做法有两种。第一种是刚才说的集合法把u到根的路径全标记然后v往上走找第一个标记点。第二种是先把两个节点提到同一深度然后一起往上走直到相遇。这两种做法单次查询的复杂度都是O(树高)。问题就出在这个树高上。如果树比较平衡高度是log级别那还行但现实中的树经常退化成一条链——比如一个层层审批的组织、一个深度嵌套的目录、一条长依赖链。这时候树高就是节点数n单次查询O(n)查询m次就是O(nm)。三万个节点、几百次查询直接就是千万级操作卡顿是必然的。所以LCA的核心矛盾就一句话能不能把单次查询从O(树高)压到O(log n)甚至O(1)代价是预处理。后面讲的所有算法本质上都是在这条权衡线上找不同的位置。2.3 哪些真实场景会用到LCA别以为这只是刷题用的。我梳理几个实际会碰到的组织架构/权限系统判断两个员工的共同上级用于审批流、权限继承、汇报关系展示。文件系统求两个路径的最近公共目录做相对路径计算、文件同步的差异定位。前端DOM操作找两个节点的最近公共父节点用于事件委托、选区处理、虚拟DOM diff。版本控制/依赖分析在提交历史或依赖树里找共同基点判断分支从哪分叉。生物信息学进化树里找物种的共同祖先。网络路由在某些树形拓扑里找共同上游节点。看出来了吧只要你的数据是树形或者能转成树形LCA就是个绕不开的基础操作。理解了它等于拿到了一把处理树形查询的万能钥匙。3. 倍增法最通用的LCA解法也是面试最爱问的3.1 倍增的核心思想用二进制跳跃代替一步步爬倍增法Binary Lifting是我最推荐的入门方案因为它通用、好写、好调而且能顺带解决一堆衍生问题比如求路径上第k个祖先、路径长度等。它的核心思想特别巧妙与其一步一步往上爬不如一次跳2的幂次步。就像你要走1000米不会一米一米挪而是先走512米、再256米……用二进制拆分快速到达。具体做法是预处理一个跳表up[i][j]表示节点i往上跳2^j步后到达的祖先。这个表可以递推出来up[i][0] parent[i] // 跳1步就是父节点 up[i][j] up[ up[i][j-1] ][j-1] // 跳2^j步 先跳2^(j-1)再跳2^(j-1)第二行的递推是整个算法的灵魂。它把跳一大步拆成跳两小步从而能用已经算好的小步结果推出大步结果。这就是典型的动态规划思想也是倍增法名字的由来。3.2 预处理一遍DFS把跳表建起来预处理分两步。第一步是DFS/BFS求出每个节点的深度depth[i]和直接父节点parent[i]。第二步就是按上面的递推式填up表。关于j的上界取LOG ceil(log2(n)) 1就够了。因为树最高n层任何跳跃需求都能用不超过log2(n)位的二进制表示。多留一位是防止边界越界。import sys sys.setrecursionlimit(300000) def preprocess(n, adj, root): LOG (n).bit_length() # 等价于 ceil(log2(n1)) depth [0] * (n 1) up [[0] * LOG for _ in range(n 1)] # 迭代式DFS避免递归爆栈 parent [0] * (n 1) order [] stack [root] visited [False] * (n 1) visited[root] True while stack: u stack.pop() order.append(u) for v in adj[u]: if not visited[v]: visited[v] True parent[v] u depth[v] depth[u] 1 stack.append(v) # 填跳表 for i in range(1, n 1): up[i][0] parent[i] for j in range(1, LOG): for i in range(1, n 1): up[i][j] up[ up[i][j-1] ][j-1] return depth, up, LOG这里有个实操细节值得说我强烈建议用迭代式DFS而不是递归。递归写起来是简洁但树一深比如退化成链Python默认递归深度1000直接爆栈C虽然栈大一些但几万层也悬。迭代式虽然代码长一点但稳。这个坑我踩过不止一次线上环境可不会给你调递归深度的机会。3.3 查询先对齐深度再一起往上跳查询LCA(u, v)分两个阶段逻辑非常清晰阶段一把深的那个提到和浅的一样深。假设depth[u] depth[v]那就把u往上跳depth[u] - depth[v]步。这个差值用二进制拆解对应到跳表上就是如果差值的第j位是1就跳2^j步。阶段二如果此时u v说明v本来就是u的祖先直接返回。否则两个节点一起往上跳从大到小尝试。关键技巧是只要跳完之后两个节点还不相等就跳。这样最后一定会停在LCA的正下方再往上一步就是答案。def lca(u, v, depth, up, LOG): if depth[u] depth[v]: u, v v, u # 阶段一对齐深度 diff depth[u] - depth[v] for j in range(LOG): if diff (1 j): u up[u][j] if u v: return u # 阶段二一起往上跳 for j in range(LOG - 1, -1, -1): if up[u][j] ! up[v][j]: u up[u][j] v up[v][j] return up[u][0]阶段二那个从大到小的循环方向特别重要必须从高位往低位试。因为我们要尽可能跳得远但又不能跳过LCA。从大往小试能保证最后停在最近的位置。如果从小到大试会跳得不够远逻辑就错了。这个细节很多人第一次写会搞反。3.4 倍增法的复杂度与适用边界预处理时间O(n log n)空间O(n log n)单次查询O(log n)。这个复杂度对于绝大多数场景都够用了。它的优势是通用性极强不要求树是静态的虽然动态更新跳表比较麻烦能处理任意形态的树还能顺便支持求第k个祖先这类操作。缺点是空间是n log n如果n到了百万级内存会有点吃紧。提示如果n特别大比如10^6以上而查询次数不多其实暴力法反而更划算。别迷信高级算法选型要看具体数据规模。4. Tarjan离线算法查询多、树不动时的效率之王4.1 离线思维把所有查询攒起来一起算倍增法是在线的——来一个查询答一个。但如果你的场景是一次性拿到所有查询然后批量出结果那Tarjan离线算法往往更快。Tarjan的核心是DFS 并查集。它利用DFS的回溯特性在遍历树的过程中顺便把所有查询都解决了。单次查询的均摊复杂度接近O(1)整体是O(n m·α(n))其中α是并查集的反阿克曼函数实际可以当成常数。这个思路的巧妙之处在于它把查询这件事融进了遍历里而不是遍历完再单独查。对于查询量巨大的场景比如m和n同量级甚至更大这个优势非常明显。4.2 并查集在这里扮演什么角色理解Tarjan的关键是搞懂并查集维护的是什么。在DFS过程中每个节点有三种状态未访问、正在访问在递归栈里、已访问完子树处理完毕。并查集维护的是已访问完的节点的集合并且每个集合的代表元指向它当前能追溯到的、还在递归栈里的那个祖先。当DFS访问到节点u处理所有跟u相关的查询(u, v)时如果v还没访问跳过等以后v被访问时再处理这对查询。如果v已经访问完了那么v所在并查集集合的代表元就是LCA(u, v)。为什么因为v已经处理完说明v的整棵子树都遍历过了而u还在栈里说明u是v的某个祖先方向上的节点。此时v能追溯到的、还在栈里的最深祖先恰好就是它和u的分叉点也就是LCA。4.3 完整实现与关键细节def tarjan_lca(n, adj, root, queries): # queries[u] [(v, query_id), ...] parent list(range(n 1)) # 并查集 ancestor [0] * (n 1) # 集合代表元对应的祖先 visited [False] * (n 1) answer [0] * len(queries) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] # 路径压缩 x parent[x] return x def dfs(u): visited[u] True ancestor[find(u)] u for v in adj[u]: if not visited[v]: dfs(v) parent[find(v)] find(u) # 合并子树到u ancestor[find(u)] u # 处理与u相关的查询 for (v, qid) in queries[u]: if visited[v]: answer[qid] ancestor[find(v)] dfs(root) return answer几个容易翻车的点第一ancestor的更新时机。每次合并完子树后要把合并后集合的ancestor重新指向u。因为合并后代表元可能变了不更新就会拿到错误的祖先。第二查询要存双向。因为处理(u,v)时可能v还没访问得等v被访问时从v那边再处理一次。所以queries[u]和queries[v]都要存这条查询。第三递归深度问题。跟倍增法一样深树会爆栈。生产环境建议改迭代或者手动加大栈空间。4.4 什么时候该选Tarjan而不是倍增判断标准很简单维度倍增法Tarjan离线查询模式在线来一个答一个离线必须预先知道所有查询单次查询O(log n)均摊O(α(n))≈O(1)预处理O(n log n)无独立预处理空间O(n log n)O(n m)实现难度中等中等偏上并查集易错适用场景查询少、需在线查询海量、可离线如果你的查询次数m远大于nTarjan的均摊优势会非常明显。但如果查询是流式的、必须即时回答那只能选倍增。选型的第一原则永远是先搞清楚你的查询模式。5. 欧拉序 RMQ把LCA变成区间最值问题5.1 一个漂亮的转化LCA等价于区间最小值这是我觉得LCA里最优雅的一个思路。它把树上问题转化成了数组上的区间查询问题。做法是对树做一次DFS记录欧拉序也叫DFS序的扩展版——每次进入一个节点记一次每次从子树返回父节点时也记一次。这样得到的序列长度是2n-1。同时记录每个节点在序列中第一次出现的位置first[u]。关键结论LCA(u, v)就是欧拉序中first[u]到first[v]这段区间里深度最小的那个节点。为什么因为从u走到v在欧拉序上必然经过它们的LCA而且LCA是这段路径上深度最小的点。这个性质把LCA问题完美地转化成了**RMQ区间最小值查询**问题。5.2 稀疏表ST表实现O(1)查询既然变成了RMQ那就可以用经典的ST表Sparse Table来做到O(1)查询。ST表的预处理是O(n log n)查询O(1)。import math def build_euler(n, adj, root): euler [] # 欧拉序存节点 depth_arr [] # 对应深度 first [0] * (n 1) visited [False] * (n 1) def dfs(u, d): visited[u] True first[u] len(euler) euler.append(u) depth_arr.append(d) for v in adj[u]: if not visited[v]: dfs(v, d 1) euler.append(u) depth_arr.append(d) dfs(root, 0) return euler, depth_arr, first def build_st(depth_arr): m len(depth_arr) LOG m.bit_length() # st[i][j] 存区间 [i, i2^j-1] 中深度最小的节点在depth_arr中的下标 st [[0] * LOG for _ in range(m)] for i in range(m): st[i][0] i for j in range(1, LOG): for i in range(m - (1 j) 1): left st[i][j-1] right st[i (1 (j-1))][j-1] st[i][j] left if depth_arr[left] depth_arr[right] else right return st def query_lca(u, v, first, depth_arr, st, euler): l, r first[u], first[v] if l r: l, r r, l length r - l 1 k length.bit_length() - 1 left st[l][k] right st[r - (1 k) 1][k] idx left if depth_arr[left] depth_arr[right] else right return euler[idx]5.3 欧拉序方案的取舍这个方案的优势是查询O(1)比倍增的O(log n)还快。而且思路清晰一旦理解了欧拉序的性质代码其实不难写。但它有几个明显的代价空间更大欧拉序长度是2n-1ST表又是(2n) log(2n)比倍增的n log n大一倍左右。预处理常数大建ST表的双重循环实际跑起来比倍增的预处理慢。只适合静态树树一变整个欧拉序和ST表都要重建。所以我的经验是如果查询量极大且树完全静态欧拉序ST表是最优解否则倍增法更省心。别为了那点查询速度提升把代码复杂度拉高一大截维护成本也是成本。注意欧拉序的DFS同样有递归深度问题。而且欧拉序长度是2n如果n很大光是存这个序列就要不少内存选型前先估一下。6. 四种解法横向对比一张表帮你做选型决策前面讲了四种主流方案这里做个系统对比方便你直接查表决策。方案预处理单次查询空间在线/离线最适合的场景暴力爬树O(1)O(树高)O(n)在线树浅、查询极少倍增法O(n log n)O(log n)O(n log n)在线通用首选查询中等Tarjan离线无均摊O(α(n))O(nm)离线查询海量、可离线欧拉序STO(n log n)O(1)O(n log n)在线查询极多、树静态选型的决策链路我一般是这么走的第一步看查询模式。流式在线查询排除Tarjan能批量离线Tarjan值得考虑。第二步看数据规模。n小几千以内且查询少暴力法最省事别过度设计。n大且查询多上倍增或欧拉序。第三步看树是否静态。树会动态变化倍增法改起来相对可控虽然也麻烦欧拉序基本要重建。第四步看查询次数。查询次数远超n欧拉序的O(1)优势才体现得出来否则倍增的O(log n)完全够用。我见过太多人一上来就写欧拉序ST表结果数据规模才几千纯属杀鸡用牛刀代码还容易写错。选型要匹配问题规模这是工程思维和刷题思维最大的区别。7. 实战中那些文档不会告诉你的坑7.1 根节点的父节点处理这是最经典的坑。根节点没有父节点那up[root][0]填什么填0假设节点编号从1开始还是填自己填0的话如果查询时不小心跳到了0后续up[0][j]全是0可能掩盖逻辑错误。填自己的话跳过头会原地打转。我的建议是填0并且在查询逻辑里保证永远不会真正用到0这个越界值——因为对齐深度和一起跳的过程理论上不会让节点跳到根之上。但为了保险可以在填表时把up[0][j]都设成0让越界访问有个确定的兜底。7.2 深度对齐时的循环方向阶段一对齐深度时for j in range(LOG)从小到大还是从大到小其实都可以因为我们是按二进制位判断的每一位独立。但阶段二一起跳的时候必须从大到小。这两个循环方向不一样很多人写着写着就混了。记住口诀对齐深度看位一起跳看大小。7.3 多组测试数据的初始化如果是在竞赛或批量处理场景多组测试数据之间一定要彻底重置所有数组。我见过因为up表没清干净上一组数据残留导致答案错误的案例。Python里重新分配数组最省心C里记得memset或者重新构造。7.4 节点编号从0还是从1开始这个看似小事实则影响巨大。从1开始的话0可以当哨兵从0开始的话就没有天然的哨兵值了。我个人的习惯是统一从1开始编号把0留作哨兵能省掉很多边界判断。如果输入是从0开始的读入时统一加1。7.5 递归改迭代的通用套路前面反复提到递归爆栈。改迭代的通用做法是手动维护一个栈栈里存(节点, 父节点, 状态)状态标记是第一次访问还是回溯。或者更简单先用BFS求出遍历顺序和父节点再按逆序处理回溯逻辑。对于倍增法其实只需要父节点和深度BFS一遍就够了根本不需要DFS。这个优化能同时解决爆栈和效率问题。8. 从LCA延伸出去几个高频衍生问题搞懂了LCA很多树上查询问题都能顺手解决。这里列几个最常见的延伸算是给你指个方向。树上两点距离。有了LCA距离公式就是depth[u] depth[v] - 2 * depth[lca(u,v)]。这个公式极其常用路径长度、树上最远点对之类的问题都靠它。树上路径第k个节点。从u到v的路径上第k个点先判断k是否超过u到LCA的距离分两种情况用倍增跳。这是倍增法跳表能力的直接应用。判断一个点是否在两点路径上。点w在u-v路径上当且仅当lca(u,w)w且lca(w,v)ww是u的祖先且是v的祖先方向或者更准确地用距离公式验证。这类判断在路径覆盖、树上差分里很常见。树上差分。给u到v的路径上所有点加一个值可以用差分diff[u] 1, diff[v] 1, diff[lca] - 1, diff[parent(lca)] - 1最后子树求和。这个技巧配合LCA能解决一大批路径统计问题。这些延伸的共同点是LCA是它们的地基。地基打牢了上面的楼怎么盖都行。所以别急着刷各种花哨的树上问题先把LCA这几种解法吃透后面会轻松很多。我个人在实际项目里的体会是真正高频用到的其实就是倍增法这一种因为它通用、在线、好维护。Tarjan和欧拉序更像是特定场景的优化手段知道原理、需要时能捡起来就行不必强求每种都背得滚瓜烂熟。把一种方案写到闭着眼睛都不出错比每种都半懂不懂要值钱得多。 LCA最近公共祖先算法详解：倍增法、Tarjan离线与欧拉序RMQ选型指南
1. 从一次线上故障说起为什么LCA值得你花时间搞懂去年帮一个朋友排查他们内部工具的一个性能问题场景很典型一个组织架构树大概三万多节点每次要计算两个员工在组织树里的最近共同上级。他们最初的实现是暴力往上爬——把A的所有祖先塞进一个集合然后B从自己开始往上走遇到的第一个在集合里的节点就是答案。单次查询看着不慢几十毫秒但架不住前端一个页面要批量算几百对页面直接卡到转圈。这个问题的本质就是LCALowest Common Ancestor最近公共祖先。听起来像是算法竞赛里的东西但只要你处理过任何树形结构——组织架构、文件目录、DOM节点、分类体系、依赖关系图——你迟早会撞上它。而且一旦数据量上去暴力解法就会原形毕露。这篇内容我打算把LCA这件事从头到尾讲透。不是那种背个倍增模板就完事的讲法而是把为什么会有多种解法、每种解法到底在权衡什么、什么场景该选哪个、写的时候哪里最容易翻车这些真正影响你落地的东西说清楚。适合已经会写基础树遍历、但一遇到树上路径查询就发怵的开发者也适合想系统梳理一遍这块知识的老手。看完你应该能做到拿到一个问题先判断它是不是LCA再根据数据规模和查询次数直接选出合适的方案而不是无脑套模板。2. LCA到底在解决什么问题把共同祖先翻译成人话2.1 用家族树理解最近公共祖先先把这个概念用最朴素的方式说清楚。想象一棵家族树根节点是最老的祖先往下每一层是下一代。现在给你两个人问他俩血缘关系最近的那个共同长辈是谁注意最近两个字是关键。往上数所有共同的长辈都算公共祖先但我们要的是**深度最大离他俩最近**的那一个。比如你和你堂哥你们的爷爷是LCA但曾祖父也是共同祖先只不过曾祖父更远不是最近的。形式化一点给定一棵有根树对于节点u和vLCA(u, v)是同时满足是u的祖先且是v的祖先的节点中深度最大的那个。这里祖先通常包含节点自己——也就是说如果u本身就是v的祖先那LCA就是u。这个约定很重要很多实现细节都跟它有关。2.2 为什么暴力爬树会崩复杂度账要算清楚最直觉的做法有两种。第一种是刚才说的集合法把u到根的路径全标记然后v往上走找第一个标记点。第二种是先把两个节点提到同一深度然后一起往上走直到相遇。这两种做法单次查询的复杂度都是O(树高)。问题就出在这个树高上。如果树比较平衡高度是log级别那还行但现实中的树经常退化成一条链——比如一个层层审批的组织、一个深度嵌套的目录、一条长依赖链。这时候树高就是节点数n单次查询O(n)查询m次就是O(nm)。三万个节点、几百次查询直接就是千万级操作卡顿是必然的。所以LCA的核心矛盾就一句话能不能把单次查询从O(树高)压到O(log n)甚至O(1)代价是预处理。后面讲的所有算法本质上都是在这条权衡线上找不同的位置。2.3 哪些真实场景会用到LCA别以为这只是刷题用的。我梳理几个实际会碰到的组织架构/权限系统判断两个员工的共同上级用于审批流、权限继承、汇报关系展示。文件系统求两个路径的最近公共目录做相对路径计算、文件同步的差异定位。前端DOM操作找两个节点的最近公共父节点用于事件委托、选区处理、虚拟DOM diff。版本控制/依赖分析在提交历史或依赖树里找共同基点判断分支从哪分叉。生物信息学进化树里找物种的共同祖先。网络路由在某些树形拓扑里找共同上游节点。看出来了吧只要你的数据是树形或者能转成树形LCA就是个绕不开的基础操作。理解了它等于拿到了一把处理树形查询的万能钥匙。3. 倍增法最通用的LCA解法也是面试最爱问的3.1 倍增的核心思想用二进制跳跃代替一步步爬倍增法Binary Lifting是我最推荐的入门方案因为它通用、好写、好调而且能顺带解决一堆衍生问题比如求路径上第k个祖先、路径长度等。它的核心思想特别巧妙与其一步一步往上爬不如一次跳2的幂次步。就像你要走1000米不会一米一米挪而是先走512米、再256米……用二进制拆分快速到达。具体做法是预处理一个跳表up[i][j]表示节点i往上跳2^j步后到达的祖先。这个表可以递推出来up[i][0] parent[i] // 跳1步就是父节点 up[i][j] up[ up[i][j-1] ][j-1] // 跳2^j步 先跳2^(j-1)再跳2^(j-1)第二行的递推是整个算法的灵魂。它把跳一大步拆成跳两小步从而能用已经算好的小步结果推出大步结果。这就是典型的动态规划思想也是倍增法名字的由来。3.2 预处理一遍DFS把跳表建起来预处理分两步。第一步是DFS/BFS求出每个节点的深度depth[i]和直接父节点parent[i]。第二步就是按上面的递推式填up表。关于j的上界取LOG ceil(log2(n)) 1就够了。因为树最高n层任何跳跃需求都能用不超过log2(n)位的二进制表示。多留一位是防止边界越界。import sys sys.setrecursionlimit(300000) def preprocess(n, adj, root): LOG (n).bit_length() # 等价于 ceil(log2(n1)) depth [0] * (n 1) up [[0] * LOG for _ in range(n 1)] # 迭代式DFS避免递归爆栈 parent [0] * (n 1) order [] stack [root] visited [False] * (n 1) visited[root] True while stack: u stack.pop() order.append(u) for v in adj[u]: if not visited[v]: visited[v] True parent[v] u depth[v] depth[u] 1 stack.append(v) # 填跳表 for i in range(1, n 1): up[i][0] parent[i] for j in range(1, LOG): for i in range(1, n 1): up[i][j] up[ up[i][j-1] ][j-1] return depth, up, LOG这里有个实操细节值得说我强烈建议用迭代式DFS而不是递归。递归写起来是简洁但树一深比如退化成链Python默认递归深度1000直接爆栈C虽然栈大一些但几万层也悬。迭代式虽然代码长一点但稳。这个坑我踩过不止一次线上环境可不会给你调递归深度的机会。3.3 查询先对齐深度再一起往上跳查询LCA(u, v)分两个阶段逻辑非常清晰阶段一把深的那个提到和浅的一样深。假设depth[u] depth[v]那就把u往上跳depth[u] - depth[v]步。这个差值用二进制拆解对应到跳表上就是如果差值的第j位是1就跳2^j步。阶段二如果此时u v说明v本来就是u的祖先直接返回。否则两个节点一起往上跳从大到小尝试。关键技巧是只要跳完之后两个节点还不相等就跳。这样最后一定会停在LCA的正下方再往上一步就是答案。def lca(u, v, depth, up, LOG): if depth[u] depth[v]: u, v v, u # 阶段一对齐深度 diff depth[u] - depth[v] for j in range(LOG): if diff (1 j): u up[u][j] if u v: return u # 阶段二一起往上跳 for j in range(LOG - 1, -1, -1): if up[u][j] ! up[v][j]: u up[u][j] v up[v][j] return up[u][0]阶段二那个从大到小的循环方向特别重要必须从高位往低位试。因为我们要尽可能跳得远但又不能跳过LCA。从大往小试能保证最后停在最近的位置。如果从小到大试会跳得不够远逻辑就错了。这个细节很多人第一次写会搞反。3.4 倍增法的复杂度与适用边界预处理时间O(n log n)空间O(n log n)单次查询O(log n)。这个复杂度对于绝大多数场景都够用了。它的优势是通用性极强不要求树是静态的虽然动态更新跳表比较麻烦能处理任意形态的树还能顺便支持求第k个祖先这类操作。缺点是空间是n log n如果n到了百万级内存会有点吃紧。提示如果n特别大比如10^6以上而查询次数不多其实暴力法反而更划算。别迷信高级算法选型要看具体数据规模。4. Tarjan离线算法查询多、树不动时的效率之王4.1 离线思维把所有查询攒起来一起算倍增法是在线的——来一个查询答一个。但如果你的场景是一次性拿到所有查询然后批量出结果那Tarjan离线算法往往更快。Tarjan的核心是DFS 并查集。它利用DFS的回溯特性在遍历树的过程中顺便把所有查询都解决了。单次查询的均摊复杂度接近O(1)整体是O(n m·α(n))其中α是并查集的反阿克曼函数实际可以当成常数。这个思路的巧妙之处在于它把查询这件事融进了遍历里而不是遍历完再单独查。对于查询量巨大的场景比如m和n同量级甚至更大这个优势非常明显。4.2 并查集在这里扮演什么角色理解Tarjan的关键是搞懂并查集维护的是什么。在DFS过程中每个节点有三种状态未访问、正在访问在递归栈里、已访问完子树处理完毕。并查集维护的是已访问完的节点的集合并且每个集合的代表元指向它当前能追溯到的、还在递归栈里的那个祖先。当DFS访问到节点u处理所有跟u相关的查询(u, v)时如果v还没访问跳过等以后v被访问时再处理这对查询。如果v已经访问完了那么v所在并查集集合的代表元就是LCA(u, v)。为什么因为v已经处理完说明v的整棵子树都遍历过了而u还在栈里说明u是v的某个祖先方向上的节点。此时v能追溯到的、还在栈里的最深祖先恰好就是它和u的分叉点也就是LCA。4.3 完整实现与关键细节def tarjan_lca(n, adj, root, queries): # queries[u] [(v, query_id), ...] parent list(range(n 1)) # 并查集 ancestor [0] * (n 1) # 集合代表元对应的祖先 visited [False] * (n 1) answer [0] * len(queries) def find(x): while parent[x] ! x: parent[x] parent[parent[x]] # 路径压缩 x parent[x] return x def dfs(u): visited[u] True ancestor[find(u)] u for v in adj[u]: if not visited[v]: dfs(v) parent[find(v)] find(u) # 合并子树到u ancestor[find(u)] u # 处理与u相关的查询 for (v, qid) in queries[u]: if visited[v]: answer[qid] ancestor[find(v)] dfs(root) return answer几个容易翻车的点第一ancestor的更新时机。每次合并完子树后要把合并后集合的ancestor重新指向u。因为合并后代表元可能变了不更新就会拿到错误的祖先。第二查询要存双向。因为处理(u,v)时可能v还没访问得等v被访问时从v那边再处理一次。所以queries[u]和queries[v]都要存这条查询。第三递归深度问题。跟倍增法一样深树会爆栈。生产环境建议改迭代或者手动加大栈空间。4.4 什么时候该选Tarjan而不是倍增判断标准很简单维度倍增法Tarjan离线查询模式在线来一个答一个离线必须预先知道所有查询单次查询O(log n)均摊O(α(n))≈O(1)预处理O(n log n)无独立预处理空间O(n log n)O(n m)实现难度中等中等偏上并查集易错适用场景查询少、需在线查询海量、可离线如果你的查询次数m远大于nTarjan的均摊优势会非常明显。但如果查询是流式的、必须即时回答那只能选倍增。选型的第一原则永远是先搞清楚你的查询模式。5. 欧拉序 RMQ把LCA变成区间最值问题5.1 一个漂亮的转化LCA等价于区间最小值这是我觉得LCA里最优雅的一个思路。它把树上问题转化成了数组上的区间查询问题。做法是对树做一次DFS记录欧拉序也叫DFS序的扩展版——每次进入一个节点记一次每次从子树返回父节点时也记一次。这样得到的序列长度是2n-1。同时记录每个节点在序列中第一次出现的位置first[u]。关键结论LCA(u, v)就是欧拉序中first[u]到first[v]这段区间里深度最小的那个节点。为什么因为从u走到v在欧拉序上必然经过它们的LCA而且LCA是这段路径上深度最小的点。这个性质把LCA问题完美地转化成了**RMQ区间最小值查询**问题。5.2 稀疏表ST表实现O(1)查询既然变成了RMQ那就可以用经典的ST表Sparse Table来做到O(1)查询。ST表的预处理是O(n log n)查询O(1)。import math def build_euler(n, adj, root): euler [] # 欧拉序存节点 depth_arr [] # 对应深度 first [0] * (n 1) visited [False] * (n 1) def dfs(u, d): visited[u] True first[u] len(euler) euler.append(u) depth_arr.append(d) for v in adj[u]: if not visited[v]: dfs(v, d 1) euler.append(u) depth_arr.append(d) dfs(root, 0) return euler, depth_arr, first def build_st(depth_arr): m len(depth_arr) LOG m.bit_length() # st[i][j] 存区间 [i, i2^j-1] 中深度最小的节点在depth_arr中的下标 st [[0] * LOG for _ in range(m)] for i in range(m): st[i][0] i for j in range(1, LOG): for i in range(m - (1 j) 1): left st[i][j-1] right st[i (1 (j-1))][j-1] st[i][j] left if depth_arr[left] depth_arr[right] else right return st def query_lca(u, v, first, depth_arr, st, euler): l, r first[u], first[v] if l r: l, r r, l length r - l 1 k length.bit_length() - 1 left st[l][k] right st[r - (1 k) 1][k] idx left if depth_arr[left] depth_arr[right] else right return euler[idx]5.3 欧拉序方案的取舍这个方案的优势是查询O(1)比倍增的O(log n)还快。而且思路清晰一旦理解了欧拉序的性质代码其实不难写。但它有几个明显的代价空间更大欧拉序长度是2n-1ST表又是(2n) log(2n)比倍增的n log n大一倍左右。预处理常数大建ST表的双重循环实际跑起来比倍增的预处理慢。只适合静态树树一变整个欧拉序和ST表都要重建。所以我的经验是如果查询量极大且树完全静态欧拉序ST表是最优解否则倍增法更省心。别为了那点查询速度提升把代码复杂度拉高一大截维护成本也是成本。注意欧拉序的DFS同样有递归深度问题。而且欧拉序长度是2n如果n很大光是存这个序列就要不少内存选型前先估一下。6. 四种解法横向对比一张表帮你做选型决策前面讲了四种主流方案这里做个系统对比方便你直接查表决策。方案预处理单次查询空间在线/离线最适合的场景暴力爬树O(1)O(树高)O(n)在线树浅、查询极少倍增法O(n log n)O(log n)O(n log n)在线通用首选查询中等Tarjan离线无均摊O(α(n))O(nm)离线查询海量、可离线欧拉序STO(n log n)O(1)O(n log n)在线查询极多、树静态选型的决策链路我一般是这么走的第一步看查询模式。流式在线查询排除Tarjan能批量离线Tarjan值得考虑。第二步看数据规模。n小几千以内且查询少暴力法最省事别过度设计。n大且查询多上倍增或欧拉序。第三步看树是否静态。树会动态变化倍增法改起来相对可控虽然也麻烦欧拉序基本要重建。第四步看查询次数。查询次数远超n欧拉序的O(1)优势才体现得出来否则倍增的O(log n)完全够用。我见过太多人一上来就写欧拉序ST表结果数据规模才几千纯属杀鸡用牛刀代码还容易写错。选型要匹配问题规模这是工程思维和刷题思维最大的区别。7. 实战中那些文档不会告诉你的坑7.1 根节点的父节点处理这是最经典的坑。根节点没有父节点那up[root][0]填什么填0假设节点编号从1开始还是填自己填0的话如果查询时不小心跳到了0后续up[0][j]全是0可能掩盖逻辑错误。填自己的话跳过头会原地打转。我的建议是填0并且在查询逻辑里保证永远不会真正用到0这个越界值——因为对齐深度和一起跳的过程理论上不会让节点跳到根之上。但为了保险可以在填表时把up[0][j]都设成0让越界访问有个确定的兜底。7.2 深度对齐时的循环方向阶段一对齐深度时for j in range(LOG)从小到大还是从大到小其实都可以因为我们是按二进制位判断的每一位独立。但阶段二一起跳的时候必须从大到小。这两个循环方向不一样很多人写着写着就混了。记住口诀对齐深度看位一起跳看大小。7.3 多组测试数据的初始化如果是在竞赛或批量处理场景多组测试数据之间一定要彻底重置所有数组。我见过因为up表没清干净上一组数据残留导致答案错误的案例。Python里重新分配数组最省心C里记得memset或者重新构造。7.4 节点编号从0还是从1开始这个看似小事实则影响巨大。从1开始的话0可以当哨兵从0开始的话就没有天然的哨兵值了。我个人的习惯是统一从1开始编号把0留作哨兵能省掉很多边界判断。如果输入是从0开始的读入时统一加1。7.5 递归改迭代的通用套路前面反复提到递归爆栈。改迭代的通用做法是手动维护一个栈栈里存(节点, 父节点, 状态)状态标记是第一次访问还是回溯。或者更简单先用BFS求出遍历顺序和父节点再按逆序处理回溯逻辑。对于倍增法其实只需要父节点和深度BFS一遍就够了根本不需要DFS。这个优化能同时解决爆栈和效率问题。8. 从LCA延伸出去几个高频衍生问题搞懂了LCA很多树上查询问题都能顺手解决。这里列几个最常见的延伸算是给你指个方向。树上两点距离。有了LCA距离公式就是depth[u] depth[v] - 2 * depth[lca(u,v)]。这个公式极其常用路径长度、树上最远点对之类的问题都靠它。树上路径第k个节点。从u到v的路径上第k个点先判断k是否超过u到LCA的距离分两种情况用倍增跳。这是倍增法跳表能力的直接应用。判断一个点是否在两点路径上。点w在u-v路径上当且仅当lca(u,w)w且lca(w,v)ww是u的祖先且是v的祖先方向或者更准确地用距离公式验证。这类判断在路径覆盖、树上差分里很常见。树上差分。给u到v的路径上所有点加一个值可以用差分diff[u] 1, diff[v] 1, diff[lca] - 1, diff[parent(lca)] - 1最后子树求和。这个技巧配合LCA能解决一大批路径统计问题。这些延伸的共同点是LCA是它们的地基。地基打牢了上面的楼怎么盖都行。所以别急着刷各种花哨的树上问题先把LCA这几种解法吃透后面会轻松很多。我个人在实际项目里的体会是真正高频用到的其实就是倍增法这一种因为它通用、在线、好维护。Tarjan和欧拉序更像是特定场景的优化手段知道原理、需要时能捡起来就行不必强求每种都背得滚瓜烂熟。把一种方案写到闭着眼睛都不出错比每种都半懂不懂要值钱得多。