Last Common Ancestor

例题:给定一棵以 $1$ 为根的树,有 $q$ 个询问,每次询问给出两个点 $u$,$v$,求这两个点的最近公共祖先。

1.定义

最近公共祖先:顾名思义,两个点的最近公共祖先(Last Commom Ancestor, LCA)是指同时是两个点的祖先的节点中深度最大的一个。
形式化的说,就是两个点共同的祖先中离它们两个最近的一个。
举个例子:

在这张图中,我们以 $1$ 为根,那么有:
$8$,$9$ 的 LCA 是 $6$;
$5$,$8$ 的 LCA 是 $2$;
$7$,$4$ 的 LCA 是 $1$;
$2$,$8$ 的 LCA 是 $2$。
其他的我就不列举了。
在这里需要注意的是,自己是自己的祖先。

这个定义应该是非常通俗易懂的。

2. 朴素做法

这个朴素做法不同于数据结构题的“暴力做法”十分无脑,它对于正解具有一定的启发作用。
首先,找出 $u$,$v$ 中深度较大的一个。
然后,让深度大的那个点一步一步往上跳,直到跳到与另一个点深度相同为止。
最后,两个点一起一步一步跳,直到跳到同一个点为止,这个点就是 $u$,$v$ 的 LCA。
很明显,这个算法的复杂度是 $O(n)$ 的,在树是一条链时被卡满。

3. 初始化

仿照 ST 表,我们定义 $f(i,j)$ 为点 $i$ 的第 $2^j$ 级祖先。形式化的说,是:
从点 $i$ 到根的链中,以 $i$ 为链底的长度为 $2^j$ 的子链的链首的父亲,也就是从 $i$ 向上跳 $2^j$ 次的结果。
显然,$\forall i$,$f(i,0)=fa_i$。
根据一点点的 DP 思想,就可以很轻松地推出:
$$ f(i,j)=f(f(i,j-1),j-1) $$
其实就是把向上跳 $2^j$ 次拆成向上跳两下 $2^{j-1}$ 次。
为了使这个 DP 式计算正确,在计算 $f(i,j)$ 时,需确保 $\forall i$,$f(i,j-1)$ 是已经被计算了的。
因此我们需要在循环外层枚举 $j$,在循环内层枚举 $i$。

1
2
3
4
5
6
for(int i=1;i<=n;i++) zx[i][0]=fa[i];
for(int j=1;j<=30;j++){
for(int i=1;i<=n;i++){
zx[i][j]=zx[zx[i][j-1]][j-1];
}
}

$2^{30}$ 次方为 int 上限的一半,肯定够用。

4. $K$ 级祖先

初始化完了,我们需要具体询问了。
目前的思路是,先让 $u,v$ 两个点中较深的一个向上跳,与另一个点同深。
为了方便起见,我们强迫 $dep_v\ge dep_u$,如果不满足,则交换 $u,v$。
此时 $v$ 需要向上跳 $cnt=dep_v-dep_u$ 次。
此时我们可以选择把 $cnt$ 转成二进制形式,然后在二进制下看,如果第 $i$ 位是 $1$,就令 $v\gets f(v,i)$。


Last Common Ancestor
https://cwhirly.github.io/2025/02/16/OI/Graph Theory/Tree Theory/Last Common Ancestor/
作者
Weihao Cheng
发布于
2025年2月16日
许可协议