图论——倍增 LCA 学习笔记

定义

最近公共祖先，简称 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. 两个点的最近公共祖先一定在这两个点的最短路上。