您的位置:首页 > 教育 > 锐评 > 中铁建设集团有限公司领导名单_文创产品设计包括哪些方面_网络营销网课_东莞关键词seo

中铁建设集团有限公司领导名单_文创产品设计包括哪些方面_网络营销网课_东莞关键词seo

2025/3/16 10:29:56 来源:https://blog.csdn.net/cyx20091026/article/details/146260889  浏览:    关键词:中铁建设集团有限公司领导名单_文创产品设计包括哪些方面_网络营销网课_东莞关键词seo
中铁建设集团有限公司领导名单_文创产品设计包括哪些方面_网络营销网课_东莞关键词seo

本文讲解用倍增法求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

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com