# LCA 公共祖先
什么是最小公共祖先，顾名思义就是俩点最近的公共祖先
如图所示：
- 2 和 5 的最小公共祖先就是 4
- 2 和 1 的最小公共祖先就是 4
- 3 和 5 的最小公共祖先是 1
那么怎么求呢？
先介绍两种朴素的做法，也就是超时的做法🐷
第一种： 向上标记法
想求两个点的最小公共祖先可以先从其中一个点往上找父亲结点，直到根节点，把路径标记一下，然后从另一个点开始做同样的操作，当遇到已经标记过的点的时候就停下来，这个点一定是最小公共祖先（ 每次查询时间复杂度：O (n) ）
# CODE
#include <bits/stdc++.h>
using namespace std;
const int MAXN=500100;
vector<int> vt[MAXN];
int fa[MAXN];
bool vis[MAXN];
void dfs(int u){
int len=vt[u].size();
for(int i=0;i<len;i++){
int v=vt[u][i];
if(v==fa[u]) continue;
fa[v]=u;
dfs(v);
}
}
int lca(int l,int r){
memset(vis,0,sizeof vis);
while(l){
vis[l]=1;
l=fa[l];
}
while(!vis[r]) r=fa[r];
return r;
}
int main()
{
ios::sync_with_stdio(0);
int n,m,s;
cin>>n>>m>>s;
for(int i=1;i<=n-1;i++){
int x,y;
cin>>x>>y;
vt[x].push_back(y);
vt[y].push_back(x);
}
dfs(s); //找到每一个点的父亲结点是谁
while(m--){
int l,r;
cin>>l>>r;
cout<<lca(l,r)<<'\n';
}
return 0;
}
第二种： 利用深度法
在上面的 dfs 函数稍微改一下，得到每一个点到根节点的深度（从 0 开始），当询问两个点的 lca 时，我们先把深度大的那个点网上搜，直到两个点的深度相同，深度相同后，两个点一起往上搜直到两个点合并到一起，那么这个点就是 lca
# CODE
#include <bits/stdc++.h> | |
using namespace std; | |
const int MAXN=500100; | |
vector<int> vt[MAXN]; | |
int fa[MAXN],dep[MAXN]; | |
void dfs(int u,int d){ | |
dep[u]=d; // 处理出每一个点的深度 | |
int len=vt[u].size(); | |
for(int i=0;i<len;i++){ | |
int v=vt[u][i]; | |
if(v==fa[u]) continue; | |
fa[v]=u; | |
dfs(v,d+1); // 子节点深度加一 | |
} | |
} | |
int lca(int l,int r){ | |
if(dep[l]<dep[r]) swap(l,r); // 保证 l 是深度大的那个点 | |
while(dep[l]>dep[r]) l=fa[l]; // 从深度大的那个开始往上走 | |
while(l!=r){ // 一起往上 | |
l=fa[l]; | |
r=fa[r]; | |
} | |
return r; | |
} | |
int main() | |
{ | |
ios::sync_with_stdio(0); | |
int n,m,s; | |
cin>>n>>m>>s; | |
for(int i=1;i<=n-1;i++){ | |
int x,y; | |
cin>>x>>y; | |
vt[x].push_back(y); | |
vt[y].push_back(x); | |
} | |
dfs(s,0); | |
while(m--){ | |
int l,r; | |
cin>>l>>r; | |
cout<<lca(l,r)<<'\n'; | |
} | |
return 0; | |
} |
# 倍增找 LCA
详细讲解：
视频
LCA 博客讲解
# P3379 【模板】最近公共祖先（LCA）
#include <bits/stdc++.h> | |
using namespace std; | |
const int MAXN=500010; | |
vector<int> ve[MAXN]; | |
int dep[MAXN],f[MAXN][22]; | |
void dfs(int u, int fa, int d){ // 找到每一个节点的父亲节点以及深度大小 | |
f[u][0]=fa; // 每一个节点往上走 2^0 步就是父亲节点 | |
dep[u]=d; // 深度 | |
int sz=ve[u].size(); // 遍历后继节点 | |
for(int i=0;i<sz;i++){ | |
int v=ve[u][i]; | |
if(v==fa) continue; // 记住不能往回走 | |
dfs(v, u, d+1); | |
} | |
} | |
void bz(int n){ // 预处理出每一个节点往上 2^i 步后到达的节点 | |
for(int i=1;i<22;i++){ //2^22 > 4e7，能处理最大深度不超过 4e7 的树 | |
for(int u=1;u<=n;u++){ | |
f[u][i]=f[f[u][i-1]][i-1]; // 当前节点向上走 2^i 步就等于先向上走 2^(i-1) 再向上走 2^(i-1) 步 | |
} | |
} | |
} | |
int lca(int x,int y){ | |
if(dep[x]<dep[y]) swap(x,y); // 保证 x 的深度大于 y | |
for(int i=log2(dep[x]-dep[y]);i>=0;i--){ | |
if((1<<i)<=dep[x]-dep[y]) x=f[x][i]; // 注意 dep [x]-dep [y] 时刻在变化，也正是因为这个所以 dep [x] 一定最后和 dep [y] | |
} | |
if(x==y) return x; | |
for(int i=log2(dep[x]);i>=0;i--){ // 此时两个节点的深度相同，就需要一起往上面走 | |
if(f[x][i]!=f[y][i]){ // 一起走 2^i 后不能相同，因为相同了可能导致超过（最近）公共祖先！ | |
x=f[x][i]; | |
y=f[y][i]; | |
} | |
} | |
// 走完后一定到达了最近公共祖先的子节点，因为这种方法本质上就是二分 | |
return f[x][0]; // 父节点就是 lca | |
} | |
int main() | |
{ | |
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); | |
int n,m,s; | |
cin>>n>>m>>s; | |
for(int i=0;i<n-1;i++){ | |
int a,b; | |
cin>>a>>b; | |
ve[a].push_back(b); | |
ve[b].push_back(a); | |
} | |
dfs(s,0,0); // 这里很巧妙哦，假设还有一个 0 节点，而 0 是 s 的父亲节点，这样每一个节点往上走 2^i 就算走过了根节点也会是 0 | |
bz(n); // 预处理 | |
while(m--){ | |
int x,y; | |
cin>>x>>y; | |
cout<<lca(x,y)<<'\n'; | |
} | |
return 0; | |
} |
