树的最近公共祖先（LCA）

最近公共祖先简称 LCA（Lowest Common Ancestor）。两个节点的最近公共祖先，就是这两个点的公共祖先里面，离根最远的那个。

为了方便，我们记某点集 $S=v_1,v_2,\cdots,v_n$ 的最近公共祖先为 $\operatorname{LCA}(v_1,v_2,\cdots,v_n)$ 或 $\operatorname{LCA}(S)$。

性质

本节部分内容翻译自 wcipeg，并做过修改。

• $\operatorname{LCA}({u})=u$；
• $u$ 是 $v$ 的祖先，当且仅当 $\operatorname{LCA}(u,v)=u$；
• 如果 $u$ 不为 $v$ 的祖先并且 $v$ 不为 $u$ 的祖先，那么 $u,v$ 分别处于 $\operatorname{LCA}(u,v)$ 的两棵不同子树中；
• 前序遍历中，$\operatorname{LCA}(S)$ 出现在所有 $S$ 中元素之前，后序遍历中 $\operatorname{LCA}(S)$ 则出现在所有 $S$ 中元素之后；
• 两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先，即 $\operatorname{LCA}(A \cup B)=\operatorname{LCA}(\operatorname{LCA}(A),\operatorname{LCA}(B))$；
• 两点的最近公共祖先必定处在树上两点间的最短路上；
• $d(u,v)=h(u)+h(v)-2h(\operatorname{LCA}(u,v))$，其中 $d$ 是树上两点间的距离，$h$ 代表某点到树根的距离。

求法

模板题：Luogu P3379。

朴素求法

先让深度较大的点“跳”上去，知道两个点的深度相同，然后再让两个点共同向上“跳”，最后一定会找到两个点的 $\operatorname{LCA}$。

预处理只需要一次 $O(n)$ 遍历，极限数据（也就是链）可以把查询卡到 $O(n)$。

倍增求法

倍增求法类似于朴素求法，唯一的区别是：朴素算法在查询时一次跳 $1$ 层，而倍增算法使用倍增的方法，一次跳 $2^n,n \in \mathbb{N}$ 层。

因为需要一次跳 $2^n,n \in \mathbb{N}$ 层，预处理时就需要处理每一个节点的第 $2^n,n \in \mathbb{N}$ 个父亲，这里用 fa[i][j] 表示节点 $i$ 的第 $2^j$ 个父亲。预处理的时间复杂度为 $O(n \log n)$，单次查询的时间复杂度为 $O(\log n)$。

这种做法有以下的卡常技巧：

• 调整 fa 数组两个维度的顺序，从而减少 cache miss 的发生；
• 通过 log 数组存储每个数的 $\log_2$ 值，减小不必要的跳转次数。

提交记录 备份

树链剖分

• size[x] 表示以 $x$ 为根的子树节点个数。
• top[x] 表示 $x$ 的所在链的顶端节点。
• son[x] 表示 $x$ 的重儿子。
• dep[x] 表示 $x$ 的深度。
• fa[x] 表示 $x$ 的父亲。
• tip[x] 表示 $x$ 剖分后的新编号，即 DFS 序。
• rank[x] 表示在线段树中第 $x$ 个点对应的树的点的编号。

提交记录 备份

用欧拉序列转化为 RMQ 问题

提交记录 备份

用 DFS 序转化为 RMQ 问题

提交记录 备份

Tarjan 算法

动态树

标准 RMQ

例题：LCA 与树上点对的距离

例题：LCA 与简单路径之间的关系

例题：LCA 与查询树上点 $u$ 到点 $v$ 的答案