题解：P3379 【模板】最近公共祖先（LCA）倍增

chu_yh · 2025-03-24 17:19:40 · 题解

update on 2025.4.20：修改了 @Fire_flys 提出的问题。详情见讨论区。

忠告：别偷懒用 AI（尤其是豆包）写题解，否则你会被格式整崩溃，比如我。

欢迎踩博客，数剖做法请见《题解：P3379 【模板】最近公共祖先（LCA）树剖》。

倍增求最近公共祖先

一棵有根树 T 的两个结点 a、b 的最近公共祖先表示一个结点 x，满足 x 是 a、b 的祖先且 x 的深度尽可能大。本题解讲解用倍增法求两节点的最近公共祖先。

暴力

首先计算出结点 a 和 b 的深度 d1 和 d2。如果 d1>d2，将 a 结点向上移动 d1-d2 步，如果 d1<d2，将 b 结点向上移动 d2-d1 步，现在 a 结点和 b 结点在同一个深度了。下面只需要同时将 a、b 结点向上移动，直到它们相遇（到达同一个结点）为止，相遇的结点即为 a、b 结点的最小公共祖先。

该算法时间复杂度为 O(nm)，对于多次询问的题目（比如本题）不能解决。

思想

倍增法其实是在上一种方法的基础上进行了优化。我们希望向上查找更快，可以事先预处理出数组 p_{u,i}，表示 u 往上移动 2^i 步到达的结点，利用 p 数组可以快速的将结点 u 向上移动 n 步，方法是将 n 表示为二进制数。

例如 n = (110)_2 ，那么利用 p 数组先向上移动 2^2 步，然后再继续移动 2^1 步，即 p_{p_{u,2},1}。这样在查找时就不用一个点一个点地往上跳，直接大跳，将大大节约时间。

求 p 数组

有定义可知：

• 当 j=0 时，p_{u,i} = fa_u，即 p[u][0]=fa_u。
• 当 j \ge 1 时，p_{u,i} = p_{p_{u,i-1},i-1}，即 p[u][i]=p[p[u][i-1]][i-1]。

其中，fa_u 是 u 节点的父亲节点。

显然，我们可以利用 DFS 或 BFS 处理出 p 数组。下面的代码使用 DFS。

void dfs(int u,int fa){//u为当前节点，fa为u节点的父亲
    d[u]=d[fa]+1,p[u][0]=fa;//d[i]表示i节点深度
    for(int i=1;(1<<i)<=d[u];i++)//不能跳出根节点，从小往大处理
        p[u][i]=p[p[u][i-1]][i-1];//核心
    for(int v:e[u]) if(v!=fa) dfs(v,u);
}

求最近公共祖先

现在要求结点 a 和 b 的最近公共祖先。

将 a 和 b 对齐

我们事先准备数组 d_u 表示 u 节点的深度。

假设 d_a \le d_b。那我们先将 b 挪到和 a 同一深度的位置。代码实现如下：

if(d[a]>d[b]) swap(a,b);//强制让b的深度更大
for(int i=20;i>=0;i--)//要把i从20到0枚举
    if(d[a]<=d[b]-(1<<i))//b向上跳后深度仍不大于a
        b=p[b][i];//b跳到p[b][i]

特别的，若此时 a、b 已重合，那这时 a 点（或 b 点）就是 a 和 b 的最近公共祖先。

if(a==b){//若a、b重合
    printf("%d\n",a);
    continue;
}

让 a 点和 b 点上跳直到它们重合