当前位置: 首页 > article >正文

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

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

P3379 【模板】最近公共祖先(LCA)

题目描述

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

输入格式

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

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

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

输出格式

输出包含 M M 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 % 30\% 30% 的数据, N ≤ 10 N\leq 10 N10 M ≤ 10 M\leq 10 M10

对于 70 % 70\% 70% 的数据, N ≤ 10000 N\leq 10000 N10000 M ≤ 10000 M\leq 10000 M10000

对于 100 % 100\% 100% 的数据, 1 ≤ N , M ≤ 500000 1 \leq N,M\leq 500000 1N,M500000 1 ≤ x , y , a , b ≤ N 1 \leq x, y,a ,b \leq N 1x,y,a,bN不保证 a ≠ b a \neq b a=b

样例说明:

该树结构如下:

第一次询问: 2 , 4 2, 4 2,4 的最近公共祖先,故为 4 4 4

第二次询问: 3 , 2 3, 2 3,2 的最近公共祖先,故为 4 4 4

第三次询问: 3 , 5 3, 5 3,5 的最近公共祖先,故为 1 1 1

第四次询问: 1 , 2 1, 2 1,2 的最近公共祖先,故为 4 4 4

第五次询问: 4 , 5 4, 5 4,5 的最近公共祖先,故为 4 4 4

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

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

解析

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

倍增

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

倍增与LCA

重要结论

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

这里,我们设 f j i f^i_j fji 为树上节点 j j j 的第 2 i 2^i 2i 代祖宗。

形象具体点说, f j 0 f^0_j fj0 j j j 点的 2 0 = 1 2^0=1 20=1 代祖宗就是爸爸, f j 1 f^1_j fj1 就是 j j j 2 1 = 2 2^1=2 21=2 代祖宗就是爷爷, f j 2 f^2_j fj2 就是 j j j 2 2 = 4 2^2=4 22=4 代祖宗就是曾曾祖父, f j 3 f^3_j fj3 就是 j j j 2 3 = 8 2^3=8 23=8 代祖宗就是曾曾曾曾曾曾祖父……

我们可以发现一个事实: f j i = f f j i − 1 i − 1 f^i_j=f^{i-1}_{f^{i-1}_j} fji=ffji1i1。 换为人话就是说 j j j 点的 2 i 2^i 2i 代祖宗就是 j j j 点的 2 i − 1 2^{i-1} 2i1 代祖宗点的 2 i − 1 2^{i-1} 2i1 代祖宗

运用

我们可以通过深搜来获取每个点的深度和 2 0 2^0 20 代祖宗。然后根据 f j i = f f j i − 1 i − 1 f^i_j=f^{i-1}_{f^{i-1}_j} fji=ffji1i1 递推算出 f j i ( i = 1 , 2 , 3 … ⌈ l o g 2 n ⌉ , j = 1 , 2 , 3 … n ) f_j^i(i=1,2,3…\lceil {log_2n}\rceil,j=1,2,3…n) fjii=1,2,3log2n,j=1,2,3n
i m a x = ⌈ l o g 2 n ⌉ i_{max}=\lceil {log_2n}\rceil imax=log2n 是因为就算树退化成一条链,最大深度也不会超过 2 ⌈ l o g 2 n ⌉ 2^{\lceil {log_2n}\rceil} 2log2n

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

假设我们要 j j j 上升 4 4 4 u u u ( 4 ) 10 = ( 100 ) 2 (4)_{10}=(100)_2 (4)10=(100)2,我们直接上升第一个 1 1 1 的位权也就是 2 2 2^2 22,到达 f j 2 = u f_j^2=u fj2=u,后面的数位都是 0 0 0 就不予考虑。
又假设要 j j j 上升 7 7 7 v v v ( 7 ) 10 = ( 111 ) 2 (7)_{10}=(111)_2 (7)10=(111)2,先上升第一个 1 1 1 的位权也就是 2 2 2^2 22,到达 f j 2 = j ′ f_j^2=j' fj2=j;再上升第二个 1 1 1 的位权也就是 2 1 2^1 21,到达 f j ′ 1 = j ′ ′ f_{j'}^1=j'' fj1=j′′;然后上升第三个 1 1 1 的位权也就是 2 0 2^0 20,到达 f j ′ ′ 0 = v f_{j''}^0=v fj′′0=v

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

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


http://www.kler.cn/a/586742.html

相关文章:

  • 链表·简单归并
  • OpenBMC:BmcWeb添加路由3 设置权限
  • 机器学习 Day05 pandas库
  • Linux 系统蓝牙音频服务实现分析
  • 基于深度学习的蛀牙智能检测与语音提示系统【python源码+Pyqt5界面+数据集+训练代码】
  • C语言数据类型取值范围及格式化符号
  • CentOS 8 停止维护后通过 rpm 包手动安装 docker
  • 《P1540 [NOIP 2010 提高组] 机器翻译 题解》
  • Scala语言的数据库编程
  • 基于雪雁算法(Snow Geese Algorithm,SGA)的多个无人机协同路径规划(可以自定义无人机数量及起始点),MATLAB代码
  • MongoDB集合(表)自动创建机制
  • ffmpeg基础整理
  • 《AI浪潮中的璀璨新星:Meta Llama、Ollama与DeepSeek的深度剖析》:此文为AI自动生成
  • 利用matlab编制的转子动力学
  • springboot树形结构 支持模糊查询,返回匹配节点和父节点,其他节点不返回
  • Android开源库——RxJava和RxAndroid
  • Training-free neural architecture search: A review
  • docker构建镜像时总会有部分文件没有被更新,解决办法
  • Android Framework 之了解系统启动流程二
  • 011【fate/extra link】【概率论与数理统计】大数定律与中心极限定理 ,数理统计的基本概念,常用的统计三大分布,正态总体的抽样分布定理