倍增LCA
LCA:已知一个树和书上两个点,求两个点的最近公共祖先。
倍增:将2的所有次幂排成一个序列,相加可以得到所有正整数,这样就可以在找最近公共祖先时不是一层一层找而是每次找2的幂次方层,大大提高算法效率。
算法思路:
1,用链式前向星存图,找到根节点并从根节点开始进行深度优先搜索,存储每个节点的深度;
2,对要查找的两个节点,先将深度较深的结点向上查找直到其深度与深度较浅的结点一致;
3,两个节点同步向上挑2的幂次方层,直到找到公共祖先。
大板子:https://www.luogu.com.cn/problem/P3379
今天心情好注释比较多。
1 #include<bits/stdc++.h> 2 #define ff(i,s,e) for(int i=s;i<=e;i++) 3 #define fff(i,s,e) for(int i=s;i>=e;i--) 4 using namespace std; 5 inline int read(){ 6 register int x=0,f=1; 7 register char ch=getchar(); 8 while(ch>'9'||ch<'0'){if(ch=='-') f=-1;ch=getchar();} 9 while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();} 10 return x*f; 11 } 12 const int N=5e5+2; 13 int n,m,s,cnt,head[N]; 14 int dep[N],f[N][21]; 15 struct qwq{ 16 int v,nxt; 17 }e[N<<1];//无向图开双倍 18 void add(int u,int v){//链式前向星存储 19 e[++cnt].v=v; 20 e[cnt].nxt=head[u]; 21 head[u]=cnt; 22 } 23 void dfs(int x,int fa){//深搜存每个节点深度 24 dep[x]=dep[fa]+1;//孩子是爹的深度+1 25 f[x][0]=fa;//更新当前x的爸爸(即2^0=1代祖宗 26 for(int i=1;(1<<i)<=dep[x];i++) f[x][i]=f[f[x][i-1]][i-1];//x的2^i代祖宗是x的2^i-1代祖宗的2^i-1代祖宗 27 for(int i=head[x];i;i=e[i].nxt) if(e[i].v!=fa) dfs(e[i].v,x);//遍历x连接的所有点为他们找爸爸 28 } 29 int lca(int x,int y){ 30 if(dep[x]<dep[y]) swap(x,y);//令x为深度较深的结点 31 fff(i,20,0) if(dep[f[x][i]]>=dep[y]) x=f[x][i];//若x的2^i级爸爸的深度大于等于y的深度,更新x 32 if(x==y) return x;//特判,x的爸爸就是y 33 fff(i,20,0) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];//若x和y的爸爸不相同,同时往上跳直到找到x和y的共同爸爸 34 return f[x][0];//返回x的爸爸 35 } 36 int main(){ 37 n=read(),m=read(),s=read(); 38 int x,y; 39 ff(i,1,n-1){ 40 x=read(),y=read(); 41 add(x,y); 42 add(y,x); 43 } 44 dfs(s,0); 45 int a,b; 46 ff(i,1,m){ 47 a=read(),b=read(); 48 printf("%d\n",lca(a,b)); 49 } 50 return 0; 51 }