P3379 【模板】最近公共祖先(LCA)【题解】(倍增法)
本文讲解用倍增法求LCA。
关于Tarjan法:P3379 【模板】最近公共祖先(LCA)【题解】(Tarjan法)
P3379 【模板】最近公共祖先(LCA)
题目描述
如题,给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。
输入格式
第一行包含三个正整数 N , M , S N,M,S N,M,S,分别表示树的结点个数、询问的个数和树根结点的序号。
接下来 N − 1 N-1 N−1 行每行包含两个正整数 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 N≤10, M ≤ 10 M\leq 10 M≤10。
对于 70 % 70\% 70% 的数据, N ≤ 10000 N\leq 10000 N≤10000, M ≤ 10000 M\leq 10000 M≤10000。
对于 100 % 100\% 100% 的数据, 1 ≤ N , M ≤ 500000 1 \leq N,M\leq 500000 1≤N,M≤500000, 1 ≤ x , y , a , b ≤ N 1 \leq x, y,a ,b \leq N 1≤x,y,a,b≤N,不保证 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=ffji−1i−1。 换为人话就是说 j j j 点的 2 i 2^i 2i 代祖宗就是 j j j 点的 2 i − 1 2^{i-1} 2i−1 代祖宗点的 2 i − 1 2^{i-1} 2i−1 代祖宗。
运用
我们可以通过深搜来获取每个点的深度和
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=ffji−1i−1 递推算出
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)
fji(i=1,2,3…⌈log2n⌉,j=1,2,3…n)
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}
2⌈log2n⌉
知道这个信息有什么用呢?
我们都知道所有十进制数都可以表示成二进制数,那么在这里,如果我们想把
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''
fj′1=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:顺序一改,就会导致算某个值时所需的值还没有得到。这和背包问题双循环原理类似