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

忠告：别偷懒用 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}=f{a}_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]。

其中，$f{a}_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$ 同一深度的位置。代码实现如下：

for(int j=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$ 点上跳直到它们重合

$a$、$b$ 利用 $p$ 数组同步上跳，直到它们重合。

for(int j=20;j>=0;j--)//也要把i从20到0枚举
    if(p[a][j]!=p[b][j])//不能重合就继续往上跳
        a=p[a][j],b=p[b][j];
printf("%d\n",p[a][0]);

为什么要把 $i$ 从 $20$ 到 $0$ 枚举？

很好理解，举个例就明白了。如：要从点 $u$ 向上跳 $666$ 步跳到 $v$。

过程：把 $i$ 从 $20$ 到 $0$ 枚举（或把 $i$ 从 $0$ 到 $20$ 枚举），若 $2^i\le x$ （即 $d_{p_{u,i}}\ge d_v$），就把 $u$ 向上跳 $2^i$ 步。

• 若是把 $i$ 从 $20$ 到 $0$ 枚举，上面的例子就会依次跳 $2^9$、$2^7$、$2^4$、$2^3$、$2^1$ 步，并且 $2^9+2^7+2^4+2^3+2^1=666$，可得把 $i$ 从 $20$ 到 $0$ 枚举是正确的。
• 若是把 $i$ 从 $0$ 到 $20$ 枚举，上面的例子就会依次跳 $2^0$、$2^2$、$2^3$、$2^4$、$2^5$、$2^6$、$2^7$、$2^8$ 步，并且 $2^0+2^1+2^3+2^4+2^5+2^6+2^7+2^8\ne 666$，可得把 $i$ 从 $0$ 到 $20$ 枚举是错误的。

看完这个例子，要把 $i$ 从 $20$ 到 $0$ 枚举的原因就不言而喻了。

完整代码

#include<bits/stdc++.h>
using namespace std;
const int N=5e6+5;
int n,m,s,d[N],p[N][21];
vector<int> e[N];

void dfs(int u,int fa){
   
	d[u]=d[fa]+1,p[u][0]=fa;
	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);
}

int main(){
   
	scanf("%d%d%d",&n,&m,&s);
	for(int i=1,x,y;i<n;i++){
   
		scanf("%d%d",&x,&y);
		e[x].push_back(y),e[y].push_back(x);
	}
	dfs(s,0);
	for(int i=1,a,b;i<=m;i++){
   
		scanf("%d%d",&a,&b);
		if(d[a]>d[b]) swap(a,b);
		for(int j=20;j>=0;j--) if(d[a]<=d[b]-(1<<j)) b=p[b][j];
		if(a==b){
   printf("%d\n",a);continue;}
		for(int j=20;j>=0;j--) if(p[a][j]!=p[b][j])	a=p[a][j],b=p[b][j];
		printf("%d\n",p[a][0]);
	}
	return 0;
}