从 LCA 谈树上倍增与重链剖分

Zskioaert1106 · 2025-03-01 20:52:35 · 算法·理论

最近公共祖先

最近公共祖先（Lowest Common Ancestor，LCA），指的是在一颗有根树中距两个结点最近的公共祖先。比如说 t=\operatorname{LCA}(x,y)，当且仅当 t 在所有 x 和 y 的公共祖先中，且 t 是深度最大（离根最远）的一个。

模板：P3379 【模板】最近公共祖先（LCA）

朴素求法

先考虑一下 \operatorname{LCA}(x,y) 的条件：

• 没有深度大于 \operatorname{LCA}(x,y) 的 x 和 y 的公共祖先。

那如何朴素求出 LCA 呢？可以重复使 x \leftarrow f\!a_{x},y \leftarrow f\!a_{y}，直到 f\!a_{x}=f\!a_{y} 即求出了。

因为 deep_{\operatorname{LCA}(x,y)}=deep_{\operatorname{LCA}(x,y)}，所以可以得出我们要先将 x 和 y 提到同一深度。

代码实现：

int lca(int x,int y){
    while(deep[x]>deep[y])x=fa[x];
    while(deep[y]>deep[x])y=fa[y];
    while(x!=y)x=fa[x],y=fa[y];
    return x;
}

容易构造出数据（如一条链，x,y 分别是链头和链尾），使得单次求 LCA 的复杂度达到 O(n)。

期望得分：TLE 100pts。

树上倍增

我们知道倍增就是存储关于 2 的幂的状态，所以单结点的时空都是 \log，从而实现 O(n \log n) 的可接受预处理范围。

对于 LCA，我们需要的信息是结点的祖先。所以可以建立二维数组，一维长度 n，一维长度 \log_2 n。定义 f_{i,j} 表示结点 i 的第 2^j 个祖先，则可以用 dp：

• 边界：f_{i,0}=f\!a_{i}（i 的第 2^0=1 个祖先）

• 状态转移：我们按 j 从小到大的顺序处理，则 f_{i,j}=f_{f_{i,j-1},j-1}。

还是将过程分为提到同层、跳到 LCA 两部分，对于第一部分，我们将 x 和 y 的深度较大者提到深度与较小者相同：

如何用已有的 2 的幂的信息求出应该怎么跳？

任何正整数都可以表现为二进制数即一些 2^i 之和（其中 i 各不相同），因此我们可以将 i 从 \log_2 n 开始，往小遍历到 0——如果 deep_{f_{x,i}}\geqslant deep_{y}，那么就可以将 x 向上提 2^i 个，即 x\leftarrow f_{x,i}。

由于 deep_x 与 deep_y 的深度差可以表示为二进制数，所以最终一定能提到指定位置。

if(deep[x]<deep[y])swap(x,y);
for(int i=l;i>=0;i--)//l 为 log2(n)
    if(deep[f[x][i]]>=deep[y])x=f[x][i];

接下来就要同时提 x 和 y，可以继续照着上面的方法提——如果 f_{x,i}\neq f_{y,i}，则将两者同时上提 2^i。但是一定要注意：

2. 最终求出来的结果是 f_{x,0}=f_{y,0} 的情况，LCA 是 f_{x,0}（或 f_{y,0}）！

3. 在开始同时提之前一定要特判如果 x=y，直接返回 x。（不然容易跑出根节点了，很显然不符合上面说的性质）