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

本文讲解用倍增法求LCA。
关于Tarjan法：P3379 【模板】最近公共祖先（LCA）【题解】(Tarjan法)

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

题目描述

如题，给定一棵有根多叉树，请求出指定两个点直接最近的公共祖先。

输入格式

第一行包含三个正整数 $N,M,S$，分别表示树的结点个数、询问的个数和树根结点的序号。

接下来 $N-1$ 行每行包含两个正整数 $x,y$，表示 $x$ 结点和 $y$ 结点之间有一条直接连接的边（数据保证可以构成树）。

接下来 $M$ 行每行包含两个正整数 $a,b$，表示询问 $a$ 结点和 $b$ 结点的最近公共祖先。

输出格式

输出包含 $M$ 行，每行包含一个正整数，依次为每一个询问的结果。

输入输出样例 #1

输入 #1

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出 #1

4
4
1
4
4

说明/提示

对于 $30\%$ 的数据，$N\le 10$，$M\le 10$。

对于 $70\%$ 的数据，$N\le 10000$，$M\le 10000$。

对于 $100\%$ 的数据，$1\le N,M\le 500000$，$1\le x,y,a,b\le N$，不保证 $a\ne b$。

样例说明：

该树结构如下：

第一次询问：$2,4$ 的最近公共祖先，故为 $4$。

第二次询问：$3,2$ 的最近公共祖先，故为 $4$。

第三次询问：$3,5$ 的最近公共祖先，故为 $1$。

第四次询问：$1,2$ 的最近公共祖先，故为 $4$。

第五次询问：$4,5$ 的最近公共祖先，故为 $4$。

故输出依次为 $4,4,1,4,4$。

2021/10/4 数据更新 @fstqwq：应要求加了两组数据卡掉了暴力跳。

解析

这是一道 $LCA$ 模板题，关于 $LCA$ 的概念等这里不再赘述，基本概念已在文初链接文章中。
这里把 $LCA(u,v)$ 想象成 $u,v$ 各自沿其树边上升第一次相遇的点

倍增

倍增可以理解为二分的逆过程。二分是每次分成两段，而倍增就是每次加一倍，成倍增加。
倍增有一个重要运用就是：$ST表$

倍增与LCA

重要结论

其实倍增的概念不清晰也并不影响本题算法的理解。

这里，我们设 $f_j^i$ 为树上节点 $j$ 的第 $2^i$ 代祖宗。

形象具体点说，$f_j^0$ 是 $j$ 点的 $2^0=1$ 代祖宗就是爸爸，$f_j^1$ 就是 $j$ 的 $2^1=2$ 代祖宗就是爷爷，$f_j^2$ 就是 $j$ 的 $2^2=4$ 代祖宗就是曾曾祖父，$f_j^3$ 就是 $j$ 的 $2^3=8$ 代祖宗就是曾曾曾曾曾曾祖父……

我们可以发现一个事实：$f_j^i=f_{f_j^{i-1}}^{i-1}$。 换为人话就是说 $j$ 点的 $2^i$ 代祖宗就是 $j$ 点的 $2^{i-1}$ 代祖宗点的 $2^{i-1}$ 代祖宗。

运用

我们可以通过深搜来获取每个点的深度和 $2^0$ 代祖宗。然后根据 $f_j^i=f_{f_j^{i-1}}^{i-1}$ 递推算出 $f_j^i（i=1,2,3\dots \lceil lo{g}_{2}n\rceil ,j=1,2,3\dots n）$
$i_{max}=\lceil lo{g}_{2}n\rceil$ 是因为就算树退化成一条链，最大深度也不会超过 $2^{\lceil lo{g}_{2}n\rceil }$

知道这个信息有什么用呢？
我们都知道所有十进制数都可以表示成二进制数，那么在这里，如果我们想把 $j$ 上升 $x$ (相当于到树上 $j$ 的 $x$ 代祖)，把这个 $x$ 表示为二进制，如果对于二进制某位有数，则上升此位的权。如此上升就能到了
如图：

假设我们要 $j$ 上升 $4$ 到 $u$ ，$(4{)}_{10}=(100{)}_2$，我们直接上升第一个 $1$ 的位权也就是$2^2$，到达$f_j^2=u$,后面的数位都是 $0$ 就不予考虑。
又假设要 $j$ 上升 $7$ 到 $v$ ，$(7{)}_{10}=(111{)}_2$，先上升第一个 $1$ 的位权也就是$2^2$，到达$f_j^2=j^{\prime }$；再上升第二个 $1$ 的位权也就是$2^1$，到达$f_{j^{\prime }}^1=j^{\prime \prime }$；然后上升第三个 $1$ 的位权也就是$2^0$，到达$f_{j^{\prime \prime }}^0=v$。

于是，对于两个点求 $LCA(u,v)$ ，先确保 $u$ 是深度较深的那个点，对于 $u$ 进行上述上升，当其深度与 $v$ 的深度相同时，先看是否已经重合了。有则直接得到答案 $LCA(u,v)=v$ 。

若没有则对 $u,v$ 同时上升一段最小的距离，使两点相同。答案就是它们重合的那个点。
因为此时 $u,v$ 深度相同，它们距离 $LCA(u,v)$ 的距离是一样的，所以同时上升相同的一段距离是会重合的。而当这段长度最小时，就是 $u,v$ 第一次相遇，也就是 $LCA(u,v)$。

代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
int n,m,s;
struct EDGE{
	int to,nxt;
}edge[MAXN];
int head[MAXN];
int tot;
int ul;//i的最大值
int d[MAXN];
int f[MAXN][20];//f[j][i]表示树上节点j的第 2的i次方 代祖宗。
void add(int u,int v){
	tot++;
	edge[tot].nxt=head[u];
	edge[tot].to=v;
	head[u]=tot; 
}
void dfs(int u,int fa){
	d[u]=d[fa]+1;f[u][0]=fa;//dfs求深度、一代祖宗
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].to;
		if(v==fa) continue;
		dfs(v,u);
	}
}
int LCA(int u,int v){
	if(d[u]<d[v]) swap(u,v);//保证u的深度大
	//由于在实际操作中不可能先算出距离的二进制，所以就对其进行枚举，从大到小，能跳大跳就先跳
	for(int i=ul;i>=0;i--){//每次跳2的i次方距离
	//思考1：为什么到达一个新点后i不重新枚举一遍
		if(d[f[u][i]]>=d[v]) u=f[u][i];//观察深度有没有超了v，没有就把u跳到那个点。
		//最后u深度一定会和v相同
	}
	if(u==v) return u;
	for(int i=ul;i>=0;i--){
		if(f[u][i]!=f[v][i]) u=f[u][i],v=f[v][i];//同时上升一段距离，每次让它不能重合
		//最后一定u,v会停在LCA(u,v)的两个子结点上
	}
	return f[u][0];//得到LCA(u,v)
}
int main(){
	cin>>n>>m>>s;
	int ui,vi;
	for(int i=1;i<n;i++){
		cin>>ui>>vi;
		add(ui,vi);
		add(vi,ui);
	}
	ul=log2(n)+1;//类似于上取整
	dfs(s,0);
	//递推
	for(int i=1;i<=ul;i++){
		//思考2：为什么双重循环必须这么写？
		for(int j=1;j<=n;j++){
			f[j][i]=f[f[j][i-1]][i-1];
		}
	}
	for(int i=1;i<=m;i++){
		cin>>ui>>vi;
		cout<<LCA(ui,vi)<<endl;
	}
	return 0;
}
//思考答案：
//1：既然跳两倍i已经试过了，就没必要再试跳i的x(x>=2)次方了
//2：顺序一改，就会导致算某个值时所需的值还没有得到。这和背包问题双循环原理类似

码字不易，能给个赞吗？QAQ