本文讲解用倍增法求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:顺序一改,就会导致算某个值时所需的值还没有得到。这和背包问题双循环原理类似