浅谈——最近公共祖先

· · 算法·理论

变量定义

不妨设 $\text{dep}_u>\text{dep}_v$。 ## 概念定义 最近公共祖先英文全称 $\tt{Lowest Common Ancestor}$，简称 $\text{LCA}$。该问题匹配有根树，对于 $u$ 和 $v$ 两节点的最近公共祖先记为 $\text{LCA}(u,v)$，表示 $u,v$ 公共祖先内最近的那个。 换句话说，如果给定根 $root$，则 $\text{LCA}$ 可以感性的理解： - 若 $v$ 是 $u$ 的祖先，则 $\text{LCA}(u,v)=v$。 - 若 $v$ 不是 $u$ 的祖先，则显然路径 $root\rightarrow u$ 和路径 $root \rightarrow v$ 一定会有一段重合，即路径 $root\rightarrow \text{LCA}(u,v)$。 ## step1.朴素法 考虑 $O(n)\sim O(n)$ 求解。 - 让 $u$ 一步一步朝父亲跳，直到深度与 $v$ 一样。 - $u$ 和 $v$ 一起朝各自的父亲跳，直到重合。 此时的 $u$ 或 $v$ 就是原来两点的 $\text{LCA}$。 预处理父亲 $O(n)$，每次查询最坏 $O(n)$。 ## step2.倍增法 考虑同样的思路。发现瓶颈在每次跳的时候直跳一步耗时间。考虑将一共跳的步数用二进制拆分。 具体来说，定义 $f_{i,j}$ 表示从点 $i$ 向 $root$ 跳 $2^j$ 步的祖先。 显然有转移 $f_{i,j}=f_{f_{i,j-1},j-1}$，表示先跳 $2^{j-1}$ 步再跳 $2^{j-1}$ 步。 那么预处理就是 $O(n \log n)$ 的。 此时原先第一步跳到一样的高度就可以 $\log n$ 解决了。考虑 $j$ 从 $\log n$ 朝 $0$ 枚举，因为如果能大跳就不用小跳浪费时间。判断当前 $u$ 向上跳 $2^j$ 的深度是比 $v$ 大还是小。大则跳，小则不跳。 然后就是同深度的了。同样考虑上述过程，如果能大跳就大跳，不能则小跳。能跳的情况就是 $u$ 和 $v$ 跳完后仍然不是同一点。 那么最后的答案就是 $f_{u,0}$ 或 $f_{v,0}$。 单次查询就是 $O(\log n)$ 的。 ## step3.树链剖分 此方法可以得到 $\text{LCA}(u,v)$ 就是两点跳到同一条重链时深度小的那个点。 预处理深度和重链是 $O(n)$，单次查询也是 $O(\log n)$。 ## step4.$\text{Tarjan}

这是一个离线算法。

离线下询问，并使用并查集。然后采用如下步骤：

初始化并查集 O(n)，由于离线，总共 q 次询问的时间复杂度是 O((n+q)\alpha(n))，\alpha(n) 极小，是路径压缩后并查集的复杂度，可以当成常数。所以询问就是 O(n+q) 的。

step5.\text{dfs} 序

考虑 $\text{dfs}$ 序的性质：祖先先于后代被遍历，即若 $u$ 是 $v$ 的祖先，$dfn_u<dfn_v$。以下记 $\text{LCA}(u,v)$ 是 $d$。 设 $dfn_u<dfn_v$（这里不遵循开头的设法）。 此时有两种情况。就是 $u,v$ 构不构成祖孙关系。 - 如果不构成祖孙关系。$\text{dfs}$ 序的顺序就是 $d \rightarrow u \rightarrow d \rightarrow v$。显然 $\text{dfs}$ 序在 $u,v$ 之间的点都属于以 $d$ 为根的子树。所以 $d\rightarrow v$ 路径上 $d$ 的儿子 $v^\prime$，找到这个 $v^\prime$（或者对应的 $u^\prime$），也就是深度最小的，它的父亲就是 $d$。 - 如果构成祖孙关系。那么 $d$ 就是 $u$。 可惜的是，我们要求深度最小的点，考虑 $\text{ST}$ 表。所以预处理 $O(n\log n)$，每次查询 $O(1)$。 貌似优秀一点的解法可以不用 $\text{ST}$ 表？具体请去[浅谈——RMQ 问题](https://www.luogu.com.cn/article/ikkdp8n5)。所以是可以 $O(n)\sim O(1)$。 ## step6.欧拉序 似乎类似 $\text{dfs}$ 序，但是难写。部分题目需要同时记录欧拉序和 $\text{dfs}$ 序。欧拉序也就是遍历顺序，节点可以重复。思路与 $\text{dfs}$ 序相同。不讲了。 ## 整理如下 |方法 |时间复杂度 |优缺点 | |:---:|:--------:|:--------:| |朴素法|$O(n)\sim O(nq)$|思路简单，但效率低| |倍增法|$O(n\log n) \sim O(q\log n)$|思路简单，效率较高，能通过大部分题| |树链剖分|$O(n)\sim O(q\log n)$|预处理复杂度低，常数小，但难写| |$\text{Tarjan}$|$O(n)\sim O(n+q)$|离线算法，复杂度优秀，但不常用| |$\text{dfs}$ 序|$O(n\log n)\sim O(q)\\O(n)\sim O(1)$|复杂度超级优秀，适合 $q$ 极大的题目| |欧拉序|$O(n\log n)\sim O(q)\\O(n)\sim O(1)$|与上个算法思路一样，但更麻烦（大众）| 习题就不放了。