本文主要是介绍C++ P3379 【模板】最近公共祖先（LCA），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：https://www.luogu.org/problemnew/show/P3379
主要是用来作为参考代码的。
#include<cstdio>
#include<iostream>
using namespace std;
int cnt=0,head[1000010],f[500010][21],d[1000010];
struct Edge{int v,nxt;
}e[1000010];//边
void addEdge(int u,int v){e[++cnt].v=v;e[cnt].nxt=head[u];head[u]=cnt;
}//建图（加边）
void dfs(int u,int fa){d[u]=d[fa]+1;//初始化点的深度 f[u][0]=fa;//结点u的往上第2^0（也就是1）为自己的直接父结点，//因此直接设置，并为之后的计算做准备 for(int i=1;(1<<i)<=d[u];i++){//循环中i的判断是否可以继续循环状态：2^1 2^2 2^3 //也就是从下往上跑深度 f[u][i]=f[f[u][i-1]][i-1];//乘法原理可得：2^（i-1）+2^（i-1）=2^（i-1)*2=2^i }for(int i=head[u];i;i=e[i].nxt){if(e[i].v!=fa)dfs(e[i].v,u);}//BFS 如果下一个点不是自己的父节点，就继续bfs
}
int lca(int a,int b){if(d[a]>d[b])swap(a,b);//先保证a的深度小于b的深度，因为可能要将其中一个较深点的位置暂时提到上面 //也就是保证b在下面，因为我们判断的是深度for(int i=20;i>=0;i--){if(d[a]<=d[b]-(1<<i))b=f[b][i];//b向上跳（因为我们保证了b在下面），一直到a与b深度相同为止.//某不科学的32位int数b:jump jump~} if(a==b)return a;//如果a和b序号相同，也就是在同一个点上//就可以返回a（或b，因为实际是一个点）了 for(int i=20;i>=0;i--){if(f[a][i]==f[b][i])continue;//同上。如果超了或到了就continue（反正就20次操作） a=f[a][i];b=f[b][i];} return f[a][0];
}
int main(){int n,m,s;scanf("%d%d%d",&n,&m,&s);for(int i=1;i<n;i++){int ta,tb;scanf("%d%d",&ta,&tb);addEdge(ta,tb);addEdge(tb,ta);}//普通的加边建图 dfs(s,0);for(int i=1;i<=m;i++){int ta,tb;scanf("%d%d",&tb,&ta);printf("%d\n",lca(ta,tb));}return 0;
}
这篇关于C++ P3379 【模板】最近公共祖先（LCA）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
