最近公共祖先
2026-03-03
简介
给定一棵树,对于树上任意两个节点 (u,v),求它们的深度最大的公共祖先。
朴素做法
对于 (u,v),让 u 先一个一个跳到根节点,同时标记所有路上的节点,然后让 v 向上跳,第一个被标记的点就是最近公共祖先。
时间复杂度 O(n)。
倍增法
很明显,我们可以使用倍增。
设 fi,j 表示节点 i 向上 2j 个节点的父亲是谁。
我们可以使用 DFS 或 BFS 初始化 fi,j。
对于一对 (u,v),我们只需要每次让深度低的向上跳尽可能多的步数,就会到达同一个深度,然后一起向上跳到有一个共同的父亲即可。
预处理 O(nlogn),单次查询 O(logn)。
Tarjan
注意:这是一个离线做法。
我们可以在 DFS 过程中顺手求出询问的 LCA。
我们把点分为三类:
- 被 DFS 过的点(已经回溯过)。
- 没被 DFS 过的点。
- 正在 DFS 的点。
首先,我们将所有询问存下来,然后对 DFS 过的点维护一个并查集。
这个时候,我们要将遍历过的点向当前正在遍历的这一串上的点连边(即将它们的父亲指向当前串上的点)。
这个时候,查询当前这一串的点只需要询问遍历过的点的父亲是谁即可。
时间复杂度 O(n+mα(n+m,n))。
