https://github.com/raineblog/blog/edit/main/docs/graph/lca/index.md

最近公共祖先

定义

最近公共祖先（LCA，Lowest Common Ancestor），顾名思义就是最近的公共祖先。

一个集合 $S$ 的最近公共祖先 $\text{LCA}(S)=\text{LCA}(s_1,s_2,\dots,s_k)$ 定义为：

这个集合中所有节点，其祖先的交集中，离根最远的那个。

性质

在数值的关系上：

1. $\text{LCA}(\{u\})=u$；
2. $\text{LCA}(A\cup B)=\text{LCA}\{\text{LCA}(A),\text{LCA}(B)\}$；
3. $d(u,v)=h(u)+h(v)-2\text{LCA}\{u,v\}$。

在形态的关系上：

1. $u$ 是 $v$ 的祖先，当且仅当 $\text{LCA}\{u,v\}=u$；
2. 两个点的最近公共祖先一定在这两个点的最短路上。

算法

由于我们可以把一个集合不断拆分，最终将问题拆分为：求任意两个点 $u,v$ 的 LCA。

朴素算法

设 $c$ 表示节点 $u,v$ 的 LCA，考虑到 $c$ 深度一定比 $u,v$ 都要小。

于是我们可以先把 $u,v$ 中比较深的那一个往上跳，最终得到 $u',v'$。

即，从两个点一步一步往上跳，跳到同一高度后再一起跳。

优化算法

很多，我们在此列举：

算法	预处理复杂度	查询复杂度	特点
倍增	$\mathcal O(n\log n)$	$\mathcal O(\log n)$	跑满 $\log$
欧拉序	$\mathcal O(n\log n)$	$\mathcal O(1)$	常数较大
DFS 序	$\mathcal O(n\log n)$	$\mathcal O(1)$	常数较小
树链剖分	$\mathcal O(n)$	$\mathcal O(\log n)$	常数很小

还有一些奇妙的，例如 Tarjan、四毛子、±1 RMQ 等，暂时不写。

• 一般来说，询问量很大的时候用 DFS 序，否则用树链剖分。

• 当求 LCA 不是复杂度瓶颈的时候，可以用倍增（好写）。

我们开始详细讲解每一个。

---

本页面最近更新：正在加载中，更新历史。
编辑页面：在 GitHub 上编辑此页！
本页面贡献者：raine。