OI-Wiki 最近公共祖先LCA详解定义、七条性质与全部经典求法【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文以 OI-Wiki 图论模块的《最近公共祖先LCA》文档docs/graph/lca.md为骨架系统讲解 LCA 的严格定义与 7 条关键性质逐一剖析朴素算法、倍增算法、Tarjan 离线算法、欧拉序列转 RMQ、树链剖分、Link Cut Tree 与标准 RMQ 等全部经典求法并对照仓库内三个完整参考实现lca_1.cpp、lca_tarjan.cpp、lca_2.cpp逐段解读代码。读完本文你将掌握每种算法的适用场景、复杂度边界与可复现的 C 实现能够根据题目规模与在线/离线需求正确选型。一、什么是 LCA定义与记号最近公共祖先Lowest Common Ancestor简称LCA的定义非常朴素两个节点的最近公共祖先就是这两个点的公共祖先里面离根最远的那一个。为了方便描述点集上的情形文档引入了如下记号记某点集 $S{v_1,v_2,\ldots,v_n}$ 的最近公共祖先为 $\text{LCA}(v_1,v_2,\ldots,v_n)$ 或 $\text{LCA}(S)$。LCA 是树上最基础、应用最广泛的问题之一树上两点最短路、树上差分、树链信息维护等大量高级算法都建立在 LCA 之上。原文档将其收录在图论模块与 树链剖分、动态树、并查集 等主题构成完整的方法论体系。二、LCA 的七条核心性质文档整理并翻译了 wcipeg 上关于 LCA 的性质清单翻译时有修改这 7 条性质是后续所有算法正确性的理论基石值得逐条理解单点情形$\text{LCA}({u})u$即单个节点构成的点集其最近公共祖先就是它自身。祖先判定$u$ 是 $v$ 的祖先当且仅当 $\text{LCA}(u,v)u$。这给出了判断祖先后代关系的充要条件。子树分离如果 $u$ 不为 $v$ 的祖先并且 $v$ 不为 $u$ 的祖先那么 $u,v$ 分别处于 $\text{LCA}(u,v)$ 的两棵不同子树中。这说明当两点不在祖先后代链上时LCA 一定分叉在二者之上。遍历序位置前序遍历中$\text{LCA}(S)$ 出现在所有 $S$ 中元素之前后序遍历中$\text{LCA}(S)$ 则出现在所有 $S$ 中元素之后。该性质与欧拉序列法见后文第七节的正确性直接相关。点集合并两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先即 $\text{LCA}(A\cup B)\text{LCA}(\text{LCA}(A), \text{LCA}(B))$。这使 LCA 具有结合性可推广到点集的多次合并查询。最短路位置两点的最近公共祖先必定处在树上两点间的最短路上因此 LCA 是求解树上最短路的天然桥梁。距离公式$d(u,v)h(u)h(v)-2h(\text{LCA}(u,v))$其中 $d$ 是树上两点间的距离$h$ 代表某点到树根的距离。这是树上两点距离的黄金公式本文第五节 HDU 2586 的参考代码就是它的直接应用。三、求法总览与复杂度对照原文档给出了从朴素到最优的完整求法谱系各算法的核心指标对比如下算法预处理复杂度单次查询复杂度查询模式朴素算法$O(n)$$\Theta(n)$与树高相关在线倍增算法$O(n\log n)$$O(\log n)$在线Tarjan 算法$O(n)$初始化并查集总复杂度 $O(m\alpha(mn,n)n)$离线欧拉序列 ST 表$O(n\log n)$$O(1)$在线树链剖分$O(n)$$O(\log n)$常数小在线Link Cut Tree——$O(\log n)$在线支持动态树标准 RMQ加减 1RMQ$O(n)$$O(1)$在线下面逐节展开每种方法的原理与实现。四、朴素算法从暴力到优化的起点过程朴素算法的思路最直观实现有两种等价的写法每次找深度比较大的那个点让它向上跳。显然在树上这两个点最后一定会相遇相遇的位置就是所求的 LCA。或者先向上调整深度较大的点令两点深度相同然后再共同向上跳转最后也一定会相遇。性质朴素算法预处理时需要 DFS 整棵树时间复杂度为 $O(n)$单次查询时间复杂度为 $\Theta(n)$。如果树满足随机性质则时间复杂度与这种随机树的期望高度有关——即随机树通常较矮暴力上跳的期望步数也随之减少。朴素算法虽然慢但它是理解倍增算法与 Tarjan 算法为什么要优化跳转的最佳起点。五、倍增算法最经典的在线求法过程倍增算法是 LCA 最经典的求法也是朴素算法的直接改进通过预处理 $\text{fa}{x,i}$ 数组表示点 $x$ 的第 $2^i$ 个祖先游标可以快速移动大幅减少了游标跳转次数。$\text{fa}{x,i}$ 数组可以通过一次 DFS 预处理出来递推关系为$$ \text{fa}{x,i}\text{fa}{\text{fa}_{x,i-1},i-1} $$即点 $x$ 的第 $2^i$ 个祖先等于 $x$ 的第 $2^{i-1}$ 个祖先的第 $2^{i-1}$ 个祖先。这样每个节点的所有幂次祖先都可以在 $O(\log n)$ 内递推得到。查询时分为两个阶段优化跳转深度对齐阶段将 $u,v$ 两点跳转到同一深度。计算出 $u,v$ 的深度之差 $y$通过将 $y$ 进行二进制拆分把 $y$ 次游标跳转优化为「$y$ 的二进制表示所含1的个数」次游标跳转。例如 $y13(1101)_2$只需按位跳 $2^32^22^0$ 三步。共同上跳阶段从最大的 $i$ 开始循环尝试一直尝试到 $0$包括 $0$。如果 $\text{fa}{u,i}\not\text{fa}{v,i}$则执行 $u\gets\text{fa}{u,i},\ v\gets\text{fa}{v,i}$。循环结束后LCA 即为 $\text{fa}{u,0}$也等于 $\text{fa}{v,0}$。性质倍增算法的预处理时间复杂度为 $O(n\log n)$单次查询时间复杂度为 $O(\log n)$且支持在线查询。文档特别指出一个工程优化点可以通过交换fa数组的两维使较小维放在前面。即把 $\text{fa}[i][x]$ 改为 $\text{fa}[x][i]$这样可以减少 cache miss 次数提高程序效率——因为同一节点不同幂次祖先在内存上更紧凑。例题HDU 2586 How far away?树上最短路查询该题要求树上任意两点间的最短距离正是性质 7 的典型应用场景可先求出 LCA再结合 $d(u,v)h(u)h(v)-2h(\text{LCA}(u,v))$ 求解也可以在求 LCA 的过程中顺便累加距离。仓库中的 lca_1.cpp 采用了后者在倍增跳转的同时维护cost数组。参考实现逐段解析doc/graph/code/lca/lca_1.cpp 是一个带边权的完整可运行实现与文档中边权累加的进阶需求对应。其预处理与查询核心如下// dfs用来为 lca 算法做准备。接受两个参数dfs 起始节点和它的父亲节点。 void dfs(int root, int fno) { // 初始化第 2^0 1 个祖先就是它的父亲节点dep 也比父亲节点多 1。 fa[root][0] fno; dep[root] dep[fa[root][0]] 1; // 初始化其他的祖先节点第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第 // 2^(i-1) 的祖先节点。 for (int i 1; i 31; i) { fa[root][i] fa[fa[root][i - 1]][i - 1]; cost[root][i] cost[fa[root][i - 1]][i - 1] cost[root][i - 1]; } // 遍历子节点来进行 dfs。 int sz v[root].size(); for (int i 0; i sz; i) { if (v[root][i] fno) continue; cost[v[root][i]][0] w[root][i]; dfs(v[root][i], root); } } // lca。用倍增算法算取 x 和 y 的 lca 节点。 int lca(int x, int y) { // 令 y 比 x 深。 if (dep[x] dep[y]) swap(x, y); // 令 y 和 x 在一个深度。 int tmp dep[y] - dep[x], ans 0; for (int j 0; tmp; j, tmp 1) if (tmp 1) ans cost[y][j], y fa[y][j]; // 如果这个时候 y x那么 xy 就都是它们自己的祖先。 if (y x) return ans; // 不然的话找到第一个不是它们祖先的两个点。 for (int j 30; j 0 y ! x; --j) { if (fa[x][j] ! fa[y][j]) { ans cost[x][j] cost[y][j]; x fa[x][j]; y fa[y][j]; } } // 返回结果。 ans cost[x][0] cost[y][0]; return ans; }需要留意代码中的几个细节二维祖先表fa[MXN][31]与cost[MXN][31]因为 $2^{30}$ 已远超 $4\times 10^4$ 的节点规模31 维足够覆盖常见数据范围。深度对齐的二进制拆分for (int j 0; tmp; j, tmp 1)循环内if (tmp 1)恰好对应深度差 $y$ 的二进制位配合cost[y][j]同步累加边权。共同上跳阶段从j 30向下枚举到 0只要fa[x][j] ! fa[y][j]就同时上跳并累加两侧边权最终 LCA 是fa[x][0]答案还需加上cost[x][0] cost[y][0]两条边。多组数据main中读取测试组数T并循环调用Solve()每组数据前用memset清空fa、cost、dep三个数组。这个实现展示了一个通用技巧倍增表可以不止维护祖先是谁还能同步维护到祖先的路径信息边权和、最值等这正是倍增思想在树上信息查询中的扩展用法。六、Tarjan 离线算法一次 DFS 回答所有询问过程Tarjan 算法是一种离线算法它借助 并查集 记录某个结点的祖先结点通过一次 DFS 遍历同时回答所有查询。文档给出的做法分为五步首先接受输入边存入邻接链表、查询边存储在另一个邻接链表内。查询边其实是虚拟加上去的边为了方便每次输入查询边的时候将这个边及其反向边都加入到queryEdge数组里。然后对其进行一次 DFS 遍历同时使用visited数组记录某个结点是否被访问过、parent记录当前结点的父亲结点。其中涉及到了回溯思想每次遍历到某个结点的时候认为这个结点的根结点就是它本身让以这个结点为根节点的 DFS 全部遍历完毕以后再将这个结点的根节点设置为这个结点的父一级结点。回溯的时候如果以该节点为起点queryEdge查询边的另一个结点也恰好访问过了则直接更新查询边的 LCA 结果。最后输出结果。核心洞察在于当 DFS 从某个子树回溯完毕、把子树根并入父节点的并查集集合后任何一端已访问、一端正在访问的查询对其 LCA 就是另一端当前所在并查集集合的代表元。性质Tarjan 算法需要初始化并查集所以预处理的时间复杂度为 $O(n)$。朴素的 Tarjan 算法处理所有 $m$ 次询问的时间复杂度为 $O(m\alpha(mn,n)n)$但 Tarjan 算法的常数比倍增算法大也存在 $O(mn)$ 的实现。文档在这里特别加了一个warning块澄清一个常见误区注意并不存在「朴素 Tarjan LCA 算法中使用的并查集性质比较特殊单次调用find()函数的时间复杂度为均摊 $O(1)$」这种说法。以下朴素 Tarjan 实现的复杂度为 $O(m\alpha(mn,n))n$。如果需要追求严格线性可以参考 Gabow 和 Tarjan 于 1983 年的论文其中给出了一种复杂度为 $O(mn)$ 的做法。这条提示提醒读者虽然很多资料笼统地说Tarjan LCA 是线性算法但朴素实现配合路径压缩并查集的严格上界仍是反阿克曼函数级追求严格线性需要更精巧的构造。参考实现逐段解析doc/graph/code/lca/lca_tarjan.cpp 给出了完整的朴素 Tarjan 实现。其数据组织方式值得注意树边和查询边都采用静态链式前向星结构Edge数组 head/queryHead头指针且查询边成对插入利用下标异或i ^ 1快速找到反向边constexpr int MAX 100; int head[MAX], queryHead[MAX]; Edge edge[MAX], queryEdge[MAX]; int parent[MAX], visited[MAX]; int find(int x) { if (parent[x] x) { return x; } else { return parent[x] find(parent[x]); // 路径压缩 } } void tarjan(int u) { parent[u] u; // 进入 u其并查集根暂时是它自己 visited[u] 1; // 先递归处理所有子结点 for (int i head[u]; i ! -1; i edge[i].next) { Edge e edge[i]; if (!visited[e.toVertex]) { tarjan(e.toVertex); parent[e.toVertex] u; // 回溯把子树根并入 u } } // 再回答所有与 u 相关的查询 for (int i queryHead[u]; i ! -1; i queryEdge[i].next) { Edge e queryEdge[i]; if (visited[e.toVertex]) { queryEdge[i ^ 1].LCA e.LCA find(e.toVertex); } } }实现要点输入阶段将每条无向树边拆成正反两条链式前向星边查询边同理成对存入queryEdge因此i ^ 1即可定位配对边。tarjan(u)先置parent[u] u完成子树递归后把每个子节点parent[e.toVertex] u这精确对应文档五步流程中的回溯再合并。回答查询时若查询边的另一端toVertex已访问则find(e.toVertex)得到的并查集代表元就是这对点的 LCA同时把结果写入正向与反向两条查询边。主函数最后按queryEdge[i * 2]输出每对查询的 LCA。七、欧拉序列转 RMQ在线 O(1) 查询定义对一棵树进行 DFS无论是第一次访问还是回溯每次到达一个结点时都将编号记录下来可以得到一个长度为 $2n-1$ 的序列这个序列被称作这棵树的欧拉序列。文档约定把结点 $u$ 在欧拉序列中第一次出现的位置编号记为 $pos(u)$也称作节点 $u$ 的欧拉序把欧拉序列本身记作 $E[1..2n-1]$。过程有了欧拉序列LCA 问题可以在线性时间内转化为 RMQ区间最值查询问题转化等式为$$ pos(\text{LCA}(u,v))\min{pos(k)\mid k\in E[pos(u)..pos(v)]} $$这个等式不难理解从 $u$ 走到 $v$ 的过程中一定会经过 $\text{LCA}(u,v)$但不会经过 $\text{LCA}(u,v)$ 的祖先。因此从 $u$ 走到 $v$ 的过程中经过的欧拉序最小的结点就是 $\text{LCA}(u,v)$。用 DFS 计算欧拉序列的时间复杂度是 $O(n)$且欧拉序列的长度也是 $O(n)$所以 LCA 问题可以在 $O(n)$ 的时间内转化成等规模的 RMQ 问题。文档内联实现ST 表原文档直接内联了基于 ST 表的参考实现这是文章中唯一一段完整内联的代码务必完整理解。它同时维护了区间最小深度st和对应节点编号revint dfn[N 1], pos[N], tot, st[30][(N 1) 2], rev[30][(N 1) 2]; // rev表示最小深度对应的节点编号 void dfs(int cur, int dep) { dfn[tot] cur; depth[tot] dep; pos[cur] tot; for (int i head[t]; i; i side[i].next) { int v side[i].to; if (!pos[v]) { dfs(v, dep 1); dfn[tot] cur, depth[tot] dep; } } } void init() { for (int i 2; i tot 1; i) lg[i] lg[i 1] 1; // 预处理 lg 代替库函数 log2 来优化常数 for (int i 1; i tot; i) st[0][i] depth[i], rev[0][i] dfn[i]; for (int i 1; i lg[tot]; i) for (int j 1; j (1 i) - 1 tot; j) if (st[i - 1][j] st[i - 1][j (1 i - 1)]) st[i][j] st[i - 1][j], rev[i][j] rev[i - 1][j]; else st[i][j] st[i - 1][j (1 i - 1)], rev[i][j] rev[i - 1][j (1 i - 1)]; } int query(int l, int r) { int k lg[r - l 1]; return st[k][l] st[k][r 1 - (1 k)] ? rev[k][l] : rev[k][r 1 - (1 k)]; }当需要查询某点对 $(u,v)$ 的 LCA 时查询区间 $[\min{pos[u],pos[v]}, \max{pos[u],pos[v]}]$ 上最小值所代表的节点即可即query(min(pos[u], pos[v]), max(pos[u], pos[v]))。几个实现细节lg数组用递推lg[i] lg[i 1] 1预处理代替库函数log2可优化常数。ST 表同时记录最小深度与该最小深度对应的节点rev数组保证查询返回的是节点编号而非深度值。用pos[v]是否非零判断节点是否首次访问兼具visited的作用。性质若使用 ST 表来解决 RMQ 问题那么该算法不支持在线修改预处理的时间复杂度为 $O(n\log n)$每次查询 LCA 的时间复杂度为 $O(1)$。八、树链剖分求 LCA原理树链剖分把树划分成若干条重链LCA 的求法非常简洁两个游标持续向上跳当它们跳转到同一条重链上时深度较小的那个游标所指向的点就是 LCA。具体来说两个游标分别沿所在重链的链头向上跳top数组每次比较链头深度较深的先跳到链头的父节点直到两个游标处于同一条重链上此时深度较浅者即为 LCA。这一过程在 OI-Wiki 的 docs/graph/hld.md 中有完整介绍仓库 docs/graph/code/hld/ 目录下也提供了对应的参考实现。性质树链剖分的预处理时间复杂度为 $O(n)$单次查询的时间复杂度为 $O(\log n)$并且常数较小。当题目本身就需要树链剖分维护链上信息时顺带用剖分求 LCA 是零额外成本的选择。九、Link Cut Tree 求 LCA原理在 Link Cut TreeLCT中设连续两次access操作的点分别为u和v则第二次access操作返回的点即为u和v的 LCA。这一结论源于 LCT 中access操作的本质它会打通从根到目标点的实链第二次access时两条实链相交的分界点正是两点的最近公共祖先。access的具体语义可参考 docs/ds/lct.md#access。性质在无link和cut等操作的情况下使用 Link Cut Tree 单次查询的时间复杂度为 $O(\log n)$。LCT 求 LCA 的价值不在于静态树的效率而在于它能处理动态加边删边场景下的 LCA 查询。十、标准 RMQO(n) ~ O(1) 的终极形态原理前面讲到了借助欧拉序将 LCA 问题转化为 RMQ 问题其瓶颈在于 RMQ。如果能做到 $O(n)\sim O(1)$ 求解 RMQ那么也就能做到 $O(n)\sim O(1)$ 求解 LCA。关键在于一个特殊性质欧拉序中相邻两数之差为 1 或者 -1。注意到这一点后就可以使用 $O(n)\sim O(1)$ 的 加减 1RMQ 来求解。所谓加减 1RMQ是指序列满足相邻元素相差为 1 时利用该特性改进 Four Russian四毛子算法做到 $O(n)\sim O(1)$ 的时间复杂度与 $O(n)$ 的空间复杂度。复杂度时间复杂度 $O(n)\sim O(1)$空间复杂度 $O(n)$支持在线查询但常数较大——因为转化步骤较多实际运行中常数往往高于 ST 表方案。例题Luogu P3379【模板】最近公共祖先LCA该模板题用于检验各算法实现的正确性与效率。仓库 lca_2.cpp 给出了基于PlusMinusOneRMQ的完整实现由 Skqliao 贡献。其整体结构为自定义的PlusMinusOneRMQ类负责分块 块间 ST 表 块内状态压缩的 O(1) RMQdfs生成欧拉序列dfn与对应深度dep查询时取两节点欧拉序区间上的最小深度节点struct PlusMinusOneRMQ { // RMQ constexpr static int M 9; int blocklen, block, Minv[N], F[N / M * 2 5][M 1], T[N], f[1 M][M][M], S[N]; void init(int n) { ... } // 分块参数与块内状态表预处理 void initmin(int a[], int n) { ... } // 构建块间 ST 表与块内压缩状态 int querymin(int a[], int L, int R) { ... } // O(1) 区间最小值查询 } rmq; int dfs_clock, dfn[N * 2], dep[N * 2], st[N]; void dfs(int u, int fa, int d) { st[u] dfs_clock; dfn[dfs_clock] u; dep[dfs_clock] d; dfs_clock; for (int i head[u]; i; i e[i].nxt) { int v e[i].v; if (v fa) continue; dfs(v, u, d 1); dfn[dfs_clock] u; dep[dfs_clock] d; dfs_clock; } } int LCA(int u, int v) { // 求解LCA int l st[u], r st[v]; if (l r) swap(l, r); return dfn[rmq.querymin(dep, l, r)]; }实现要点PlusMinusOneRMQ::init中blocklen log2(n)/2决定分块大小f[1 (blocklen - 1)][blocklen][blocklen]是块内所有可能形态由相邻差分压缩成的状态的预计算结果表T[i]是预处理的log2表。dfs(s, s, 0)从根s出发生成欧拉序st[u]记录节点u第一次出现的位置欧拉序与第七节中的pos(u)完全对应。查询LCA(u, v)只需把[st[u], st[v]]区间交给querymin返回的深度最小位置再映射回节点编号dfn[...]。十一、实战习题原文档在结尾给出了三道循序渐进的练习均可直接检验本文所学祖孙询问给定一棵树与若干询问判断两个节点是否存在祖先后代关系——直接用性质 2$\text{LCA}(u,v)u$ 当且仅当 $u$ 是 $v$ 的祖先即可判定。货车运输经典的树上路径瓶颈问题通常先构造最大生成树再在树上用倍增维护路径边权最小值是倍增思想从维护祖先扩展到维护路径信息的典型训练。点的距离树上两点间距离查询直接套用性质 7 的距离公式 $d(u,v)h(u)h(v)-2h(\text{LCA}(u,v))$。十二、选型建议与延伸阅读综合原文档全部分析可以给出如下选型建议静态树 在线查询首选倍增算法实现简单、$O(\log n)$ 稳定追求 $O(1)$ 查询可选欧拉序列 ST 表询问全部已知离线Tarjan 算法一次 DFS 回答所有询问但注意其朴素实现的复杂度上界含反阿克曼函数需要维护链上信息或动态树分别选择树链剖分常数小、可维护链信息或 Link Cut Tree支持加删边追求理论最优利用欧拉序列相邻差为 ±1 的特性用加减 1RMQ 达到 $O(n)\sim O(1)$。进一步延伸可阅读仓库内的关联主题并查集Tarjan 算法的基础、Link Cut Treeaccess 求 LCA、树链剖分重链跳转求 LCA、加减 1RMQ 与 RMQ 专题以及本文三个完整参考实现 lca_1.cpp、lca_tarjan.cpp、lca_2.cpp它们与 docs/graph/lca.md 一起构成了完整的 LCA 学习闭环。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/13 7:20:36 · 阅读 1.2k OI-Wiki 最近公共祖先（LCA）详解：定义、七条性质与全部经典求法
OI-Wiki 最近公共祖先LCA详解定义、七条性质与全部经典求法【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki导读本文以 OI-Wiki 图论模块的《最近公共祖先LCA》文档docs/graph/lca.md为骨架系统讲解 LCA 的严格定义与 7 条关键性质逐一剖析朴素算法、倍增算法、Tarjan 离线算法、欧拉序列转 RMQ、树链剖分、Link Cut Tree 与标准 RMQ 等全部经典求法并对照仓库内三个完整参考实现lca_1.cpp、lca_tarjan.cpp、lca_2.cpp逐段解读代码。读完本文你将掌握每种算法的适用场景、复杂度边界与可复现的 C 实现能够根据题目规模与在线/离线需求正确选型。一、什么是 LCA定义与记号最近公共祖先Lowest Common Ancestor简称LCA的定义非常朴素两个节点的最近公共祖先就是这两个点的公共祖先里面离根最远的那一个。为了方便描述点集上的情形文档引入了如下记号记某点集 $S{v_1,v_2,\ldots,v_n}$ 的最近公共祖先为 $\text{LCA}(v_1,v_2,\ldots,v_n)$ 或 $\text{LCA}(S)$。LCA 是树上最基础、应用最广泛的问题之一树上两点最短路、树上差分、树链信息维护等大量高级算法都建立在 LCA 之上。原文档将其收录在图论模块与 树链剖分、动态树、并查集 等主题构成完整的方法论体系。二、LCA 的七条核心性质文档整理并翻译了 wcipeg 上关于 LCA 的性质清单翻译时有修改这 7 条性质是后续所有算法正确性的理论基石值得逐条理解单点情形$\text{LCA}({u})u$即单个节点构成的点集其最近公共祖先就是它自身。祖先判定$u$ 是 $v$ 的祖先当且仅当 $\text{LCA}(u,v)u$。这给出了判断祖先后代关系的充要条件。子树分离如果 $u$ 不为 $v$ 的祖先并且 $v$ 不为 $u$ 的祖先那么 $u,v$ 分别处于 $\text{LCA}(u,v)$ 的两棵不同子树中。这说明当两点不在祖先后代链上时LCA 一定分叉在二者之上。遍历序位置前序遍历中$\text{LCA}(S)$ 出现在所有 $S$ 中元素之前后序遍历中$\text{LCA}(S)$ 则出现在所有 $S$ 中元素之后。该性质与欧拉序列法见后文第七节的正确性直接相关。点集合并两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先即 $\text{LCA}(A\cup B)\text{LCA}(\text{LCA}(A), \text{LCA}(B))$。这使 LCA 具有结合性可推广到点集的多次合并查询。最短路位置两点的最近公共祖先必定处在树上两点间的最短路上因此 LCA 是求解树上最短路的天然桥梁。距离公式$d(u,v)h(u)h(v)-2h(\text{LCA}(u,v))$其中 $d$ 是树上两点间的距离$h$ 代表某点到树根的距离。这是树上两点距离的黄金公式本文第五节 HDU 2586 的参考代码就是它的直接应用。三、求法总览与复杂度对照原文档给出了从朴素到最优的完整求法谱系各算法的核心指标对比如下算法预处理复杂度单次查询复杂度查询模式朴素算法$O(n)$$\Theta(n)$与树高相关在线倍增算法$O(n\log n)$$O(\log n)$在线Tarjan 算法$O(n)$初始化并查集总复杂度 $O(m\alpha(mn,n)n)$离线欧拉序列 ST 表$O(n\log n)$$O(1)$在线树链剖分$O(n)$$O(\log n)$常数小在线Link Cut Tree——$O(\log n)$在线支持动态树标准 RMQ加减 1RMQ$O(n)$$O(1)$在线下面逐节展开每种方法的原理与实现。四、朴素算法从暴力到优化的起点过程朴素算法的思路最直观实现有两种等价的写法每次找深度比较大的那个点让它向上跳。显然在树上这两个点最后一定会相遇相遇的位置就是所求的 LCA。或者先向上调整深度较大的点令两点深度相同然后再共同向上跳转最后也一定会相遇。性质朴素算法预处理时需要 DFS 整棵树时间复杂度为 $O(n)$单次查询时间复杂度为 $\Theta(n)$。如果树满足随机性质则时间复杂度与这种随机树的期望高度有关——即随机树通常较矮暴力上跳的期望步数也随之减少。朴素算法虽然慢但它是理解倍增算法与 Tarjan 算法为什么要优化跳转的最佳起点。五、倍增算法最经典的在线求法过程倍增算法是 LCA 最经典的求法也是朴素算法的直接改进通过预处理 $\text{fa}{x,i}$ 数组表示点 $x$ 的第 $2^i$ 个祖先游标可以快速移动大幅减少了游标跳转次数。$\text{fa}{x,i}$ 数组可以通过一次 DFS 预处理出来递推关系为$$ \text{fa}{x,i}\text{fa}{\text{fa}_{x,i-1},i-1} $$即点 $x$ 的第 $2^i$ 个祖先等于 $x$ 的第 $2^{i-1}$ 个祖先的第 $2^{i-1}$ 个祖先。这样每个节点的所有幂次祖先都可以在 $O(\log n)$ 内递推得到。查询时分为两个阶段优化跳转深度对齐阶段将 $u,v$ 两点跳转到同一深度。计算出 $u,v$ 的深度之差 $y$通过将 $y$ 进行二进制拆分把 $y$ 次游标跳转优化为「$y$ 的二进制表示所含1的个数」次游标跳转。例如 $y13(1101)_2$只需按位跳 $2^32^22^0$ 三步。共同上跳阶段从最大的 $i$ 开始循环尝试一直尝试到 $0$包括 $0$。如果 $\text{fa}{u,i}\not\text{fa}{v,i}$则执行 $u\gets\text{fa}{u,i},\ v\gets\text{fa}{v,i}$。循环结束后LCA 即为 $\text{fa}{u,0}$也等于 $\text{fa}{v,0}$。性质倍增算法的预处理时间复杂度为 $O(n\log n)$单次查询时间复杂度为 $O(\log n)$且支持在线查询。文档特别指出一个工程优化点可以通过交换fa数组的两维使较小维放在前面。即把 $\text{fa}[i][x]$ 改为 $\text{fa}[x][i]$这样可以减少 cache miss 次数提高程序效率——因为同一节点不同幂次祖先在内存上更紧凑。例题HDU 2586 How far away?树上最短路查询该题要求树上任意两点间的最短距离正是性质 7 的典型应用场景可先求出 LCA再结合 $d(u,v)h(u)h(v)-2h(\text{LCA}(u,v))$ 求解也可以在求 LCA 的过程中顺便累加距离。仓库中的 lca_1.cpp 采用了后者在倍增跳转的同时维护cost数组。参考实现逐段解析doc/graph/code/lca/lca_1.cpp 是一个带边权的完整可运行实现与文档中边权累加的进阶需求对应。其预处理与查询核心如下// dfs用来为 lca 算法做准备。接受两个参数dfs 起始节点和它的父亲节点。 void dfs(int root, int fno) { // 初始化第 2^0 1 个祖先就是它的父亲节点dep 也比父亲节点多 1。 fa[root][0] fno; dep[root] dep[fa[root][0]] 1; // 初始化其他的祖先节点第 2^i 的祖先节点是第 2^(i-1) 的祖先节点的第 // 2^(i-1) 的祖先节点。 for (int i 1; i 31; i) { fa[root][i] fa[fa[root][i - 1]][i - 1]; cost[root][i] cost[fa[root][i - 1]][i - 1] cost[root][i - 1]; } // 遍历子节点来进行 dfs。 int sz v[root].size(); for (int i 0; i sz; i) { if (v[root][i] fno) continue; cost[v[root][i]][0] w[root][i]; dfs(v[root][i], root); } } // lca。用倍增算法算取 x 和 y 的 lca 节点。 int lca(int x, int y) { // 令 y 比 x 深。 if (dep[x] dep[y]) swap(x, y); // 令 y 和 x 在一个深度。 int tmp dep[y] - dep[x], ans 0; for (int j 0; tmp; j, tmp 1) if (tmp 1) ans cost[y][j], y fa[y][j]; // 如果这个时候 y x那么 xy 就都是它们自己的祖先。 if (y x) return ans; // 不然的话找到第一个不是它们祖先的两个点。 for (int j 30; j 0 y ! x; --j) { if (fa[x][j] ! fa[y][j]) { ans cost[x][j] cost[y][j]; x fa[x][j]; y fa[y][j]; } } // 返回结果。 ans cost[x][0] cost[y][0]; return ans; }需要留意代码中的几个细节二维祖先表fa[MXN][31]与cost[MXN][31]因为 $2^{30}$ 已远超 $4\times 10^4$ 的节点规模31 维足够覆盖常见数据范围。深度对齐的二进制拆分for (int j 0; tmp; j, tmp 1)循环内if (tmp 1)恰好对应深度差 $y$ 的二进制位配合cost[y][j]同步累加边权。共同上跳阶段从j 30向下枚举到 0只要fa[x][j] ! fa[y][j]就同时上跳并累加两侧边权最终 LCA 是fa[x][0]答案还需加上cost[x][0] cost[y][0]两条边。多组数据main中读取测试组数T并循环调用Solve()每组数据前用memset清空fa、cost、dep三个数组。这个实现展示了一个通用技巧倍增表可以不止维护祖先是谁还能同步维护到祖先的路径信息边权和、最值等这正是倍增思想在树上信息查询中的扩展用法。六、Tarjan 离线算法一次 DFS 回答所有询问过程Tarjan 算法是一种离线算法它借助 并查集 记录某个结点的祖先结点通过一次 DFS 遍历同时回答所有查询。文档给出的做法分为五步首先接受输入边存入邻接链表、查询边存储在另一个邻接链表内。查询边其实是虚拟加上去的边为了方便每次输入查询边的时候将这个边及其反向边都加入到queryEdge数组里。然后对其进行一次 DFS 遍历同时使用visited数组记录某个结点是否被访问过、parent记录当前结点的父亲结点。其中涉及到了回溯思想每次遍历到某个结点的时候认为这个结点的根结点就是它本身让以这个结点为根节点的 DFS 全部遍历完毕以后再将这个结点的根节点设置为这个结点的父一级结点。回溯的时候如果以该节点为起点queryEdge查询边的另一个结点也恰好访问过了则直接更新查询边的 LCA 结果。最后输出结果。核心洞察在于当 DFS 从某个子树回溯完毕、把子树根并入父节点的并查集集合后任何一端已访问、一端正在访问的查询对其 LCA 就是另一端当前所在并查集集合的代表元。性质Tarjan 算法需要初始化并查集所以预处理的时间复杂度为 $O(n)$。朴素的 Tarjan 算法处理所有 $m$ 次询问的时间复杂度为 $O(m\alpha(mn,n)n)$但 Tarjan 算法的常数比倍增算法大也存在 $O(mn)$ 的实现。文档在这里特别加了一个warning块澄清一个常见误区注意并不存在「朴素 Tarjan LCA 算法中使用的并查集性质比较特殊单次调用find()函数的时间复杂度为均摊 $O(1)$」这种说法。以下朴素 Tarjan 实现的复杂度为 $O(m\alpha(mn,n))n$。如果需要追求严格线性可以参考 Gabow 和 Tarjan 于 1983 年的论文其中给出了一种复杂度为 $O(mn)$ 的做法。这条提示提醒读者虽然很多资料笼统地说Tarjan LCA 是线性算法但朴素实现配合路径压缩并查集的严格上界仍是反阿克曼函数级追求严格线性需要更精巧的构造。参考实现逐段解析doc/graph/code/lca/lca_tarjan.cpp 给出了完整的朴素 Tarjan 实现。其数据组织方式值得注意树边和查询边都采用静态链式前向星结构Edge数组 head/queryHead头指针且查询边成对插入利用下标异或i ^ 1快速找到反向边constexpr int MAX 100; int head[MAX], queryHead[MAX]; Edge edge[MAX], queryEdge[MAX]; int parent[MAX], visited[MAX]; int find(int x) { if (parent[x] x) { return x; } else { return parent[x] find(parent[x]); // 路径压缩 } } void tarjan(int u) { parent[u] u; // 进入 u其并查集根暂时是它自己 visited[u] 1; // 先递归处理所有子结点 for (int i head[u]; i ! -1; i edge[i].next) { Edge e edge[i]; if (!visited[e.toVertex]) { tarjan(e.toVertex); parent[e.toVertex] u; // 回溯把子树根并入 u } } // 再回答所有与 u 相关的查询 for (int i queryHead[u]; i ! -1; i queryEdge[i].next) { Edge e queryEdge[i]; if (visited[e.toVertex]) { queryEdge[i ^ 1].LCA e.LCA find(e.toVertex); } } }实现要点输入阶段将每条无向树边拆成正反两条链式前向星边查询边同理成对存入queryEdge因此i ^ 1即可定位配对边。tarjan(u)先置parent[u] u完成子树递归后把每个子节点parent[e.toVertex] u这精确对应文档五步流程中的回溯再合并。回答查询时若查询边的另一端toVertex已访问则find(e.toVertex)得到的并查集代表元就是这对点的 LCA同时把结果写入正向与反向两条查询边。主函数最后按queryEdge[i * 2]输出每对查询的 LCA。七、欧拉序列转 RMQ在线 O(1) 查询定义对一棵树进行 DFS无论是第一次访问还是回溯每次到达一个结点时都将编号记录下来可以得到一个长度为 $2n-1$ 的序列这个序列被称作这棵树的欧拉序列。文档约定把结点 $u$ 在欧拉序列中第一次出现的位置编号记为 $pos(u)$也称作节点 $u$ 的欧拉序把欧拉序列本身记作 $E[1..2n-1]$。过程有了欧拉序列LCA 问题可以在线性时间内转化为 RMQ区间最值查询问题转化等式为$$ pos(\text{LCA}(u,v))\min{pos(k)\mid k\in E[pos(u)..pos(v)]} $$这个等式不难理解从 $u$ 走到 $v$ 的过程中一定会经过 $\text{LCA}(u,v)$但不会经过 $\text{LCA}(u,v)$ 的祖先。因此从 $u$ 走到 $v$ 的过程中经过的欧拉序最小的结点就是 $\text{LCA}(u,v)$。用 DFS 计算欧拉序列的时间复杂度是 $O(n)$且欧拉序列的长度也是 $O(n)$所以 LCA 问题可以在 $O(n)$ 的时间内转化成等规模的 RMQ 问题。文档内联实现ST 表原文档直接内联了基于 ST 表的参考实现这是文章中唯一一段完整内联的代码务必完整理解。它同时维护了区间最小深度st和对应节点编号revint dfn[N 1], pos[N], tot, st[30][(N 1) 2], rev[30][(N 1) 2]; // rev表示最小深度对应的节点编号 void dfs(int cur, int dep) { dfn[tot] cur; depth[tot] dep; pos[cur] tot; for (int i head[t]; i; i side[i].next) { int v side[i].to; if (!pos[v]) { dfs(v, dep 1); dfn[tot] cur, depth[tot] dep; } } } void init() { for (int i 2; i tot 1; i) lg[i] lg[i 1] 1; // 预处理 lg 代替库函数 log2 来优化常数 for (int i 1; i tot; i) st[0][i] depth[i], rev[0][i] dfn[i]; for (int i 1; i lg[tot]; i) for (int j 1; j (1 i) - 1 tot; j) if (st[i - 1][j] st[i - 1][j (1 i - 1)]) st[i][j] st[i - 1][j], rev[i][j] rev[i - 1][j]; else st[i][j] st[i - 1][j (1 i - 1)], rev[i][j] rev[i - 1][j (1 i - 1)]; } int query(int l, int r) { int k lg[r - l 1]; return st[k][l] st[k][r 1 - (1 k)] ? rev[k][l] : rev[k][r 1 - (1 k)]; }当需要查询某点对 $(u,v)$ 的 LCA 时查询区间 $[\min{pos[u],pos[v]}, \max{pos[u],pos[v]}]$ 上最小值所代表的节点即可即query(min(pos[u], pos[v]), max(pos[u], pos[v]))。几个实现细节lg数组用递推lg[i] lg[i 1] 1预处理代替库函数log2可优化常数。ST 表同时记录最小深度与该最小深度对应的节点rev数组保证查询返回的是节点编号而非深度值。用pos[v]是否非零判断节点是否首次访问兼具visited的作用。性质若使用 ST 表来解决 RMQ 问题那么该算法不支持在线修改预处理的时间复杂度为 $O(n\log n)$每次查询 LCA 的时间复杂度为 $O(1)$。八、树链剖分求 LCA原理树链剖分把树划分成若干条重链LCA 的求法非常简洁两个游标持续向上跳当它们跳转到同一条重链上时深度较小的那个游标所指向的点就是 LCA。具体来说两个游标分别沿所在重链的链头向上跳top数组每次比较链头深度较深的先跳到链头的父节点直到两个游标处于同一条重链上此时深度较浅者即为 LCA。这一过程在 OI-Wiki 的 docs/graph/hld.md 中有完整介绍仓库 docs/graph/code/hld/ 目录下也提供了对应的参考实现。性质树链剖分的预处理时间复杂度为 $O(n)$单次查询的时间复杂度为 $O(\log n)$并且常数较小。当题目本身就需要树链剖分维护链上信息时顺带用剖分求 LCA 是零额外成本的选择。九、Link Cut Tree 求 LCA原理在 Link Cut TreeLCT中设连续两次access操作的点分别为u和v则第二次access操作返回的点即为u和v的 LCA。这一结论源于 LCT 中access操作的本质它会打通从根到目标点的实链第二次access时两条实链相交的分界点正是两点的最近公共祖先。access的具体语义可参考 docs/ds/lct.md#access。性质在无link和cut等操作的情况下使用 Link Cut Tree 单次查询的时间复杂度为 $O(\log n)$。LCT 求 LCA 的价值不在于静态树的效率而在于它能处理动态加边删边场景下的 LCA 查询。十、标准 RMQO(n) ~ O(1) 的终极形态原理前面讲到了借助欧拉序将 LCA 问题转化为 RMQ 问题其瓶颈在于 RMQ。如果能做到 $O(n)\sim O(1)$ 求解 RMQ那么也就能做到 $O(n)\sim O(1)$ 求解 LCA。关键在于一个特殊性质欧拉序中相邻两数之差为 1 或者 -1。注意到这一点后就可以使用 $O(n)\sim O(1)$ 的 加减 1RMQ 来求解。所谓加减 1RMQ是指序列满足相邻元素相差为 1 时利用该特性改进 Four Russian四毛子算法做到 $O(n)\sim O(1)$ 的时间复杂度与 $O(n)$ 的空间复杂度。复杂度时间复杂度 $O(n)\sim O(1)$空间复杂度 $O(n)$支持在线查询但常数较大——因为转化步骤较多实际运行中常数往往高于 ST 表方案。例题Luogu P3379【模板】最近公共祖先LCA该模板题用于检验各算法实现的正确性与效率。仓库 lca_2.cpp 给出了基于PlusMinusOneRMQ的完整实现由 Skqliao 贡献。其整体结构为自定义的PlusMinusOneRMQ类负责分块 块间 ST 表 块内状态压缩的 O(1) RMQdfs生成欧拉序列dfn与对应深度dep查询时取两节点欧拉序区间上的最小深度节点struct PlusMinusOneRMQ { // RMQ constexpr static int M 9; int blocklen, block, Minv[N], F[N / M * 2 5][M 1], T[N], f[1 M][M][M], S[N]; void init(int n) { ... } // 分块参数与块内状态表预处理 void initmin(int a[], int n) { ... } // 构建块间 ST 表与块内压缩状态 int querymin(int a[], int L, int R) { ... } // O(1) 区间最小值查询 } rmq; int dfs_clock, dfn[N * 2], dep[N * 2], st[N]; void dfs(int u, int fa, int d) { st[u] dfs_clock; dfn[dfs_clock] u; dep[dfs_clock] d; dfs_clock; for (int i head[u]; i; i e[i].nxt) { int v e[i].v; if (v fa) continue; dfs(v, u, d 1); dfn[dfs_clock] u; dep[dfs_clock] d; dfs_clock; } } int LCA(int u, int v) { // 求解LCA int l st[u], r st[v]; if (l r) swap(l, r); return dfn[rmq.querymin(dep, l, r)]; }实现要点PlusMinusOneRMQ::init中blocklen log2(n)/2决定分块大小f[1 (blocklen - 1)][blocklen][blocklen]是块内所有可能形态由相邻差分压缩成的状态的预计算结果表T[i]是预处理的log2表。dfs(s, s, 0)从根s出发生成欧拉序st[u]记录节点u第一次出现的位置欧拉序与第七节中的pos(u)完全对应。查询LCA(u, v)只需把[st[u], st[v]]区间交给querymin返回的深度最小位置再映射回节点编号dfn[...]。十一、实战习题原文档在结尾给出了三道循序渐进的练习均可直接检验本文所学祖孙询问给定一棵树与若干询问判断两个节点是否存在祖先后代关系——直接用性质 2$\text{LCA}(u,v)u$ 当且仅当 $u$ 是 $v$ 的祖先即可判定。货车运输经典的树上路径瓶颈问题通常先构造最大生成树再在树上用倍增维护路径边权最小值是倍增思想从维护祖先扩展到维护路径信息的典型训练。点的距离树上两点间距离查询直接套用性质 7 的距离公式 $d(u,v)h(u)h(v)-2h(\text{LCA}(u,v))$。十二、选型建议与延伸阅读综合原文档全部分析可以给出如下选型建议静态树 在线查询首选倍增算法实现简单、$O(\log n)$ 稳定追求 $O(1)$ 查询可选欧拉序列 ST 表询问全部已知离线Tarjan 算法一次 DFS 回答所有询问但注意其朴素实现的复杂度上界含反阿克曼函数需要维护链上信息或动态树分别选择树链剖分常数小、可维护链信息或 Link Cut Tree支持加删边追求理论最优利用欧拉序列相邻差为 ±1 的特性用加减 1RMQ 达到 $O(n)\sim O(1)$。进一步延伸可阅读仓库内的关联主题并查集Tarjan 算法的基础、Link Cut Treeaccess 求 LCA、树链剖分重链跳转求 LCA、加减 1RMQ 与 RMQ 专题以及本文三个完整参考实现 lca_1.cpp、lca_tarjan.cpp、lca_2.cpp它们与 docs/graph/lca.md 一起构成了完整的 LCA 学习闭环。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考