当前位置：首页 > news >正文

最近公共祖先 (LCA)

news 2026/5/12 19:10:00

\(update : 2025/10/28\)

最近公共祖先, 即 \(LCA\) (\(Least\; Common\; Ancestor\)), 顾名思义, 用于在一棵树中求两个点的最近公共祖先

方法有很多, 效率和码量各有千秋

倍增法

很经典的 \(lca\) 求法, 主要是好理解, 好打, 复杂度不优

复杂度

时间 : \(O(n \log n)\) 预处理, \(O(\log n)\) 单次查询

空间 : \(O(n \log n)\)

原理

基于倍增的方法, 记录每个节点的 \(2^k\) 级祖先, 查询时先将两节点跳到同一高度, 随后一起向上查询祖先

小优化

可以预处理出 \(\log\) 的数组, 随后通过一些小技巧来减少枚举次数

这个优化只是常数级别

\(code\)

这个代码主要是便于理解, 但是常数巨大

//May all the beauty be blessed.
#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
int n,m,s;
vector<int> a[500010];
int f[500010][35],dis[500010];void dfs(int x,int fa){ //遍历图 dis[x]=dis[fa]+1;f[x][0]=fa;for(int i=1;i<=30;i++){ //处理 f[x][i]=f[f[x][i-1]][i-1];}for(auto i:a[x]){if(fa==i) continue;dfs(i,x);}
}int lca(int x,int y){if(dis[x]<dis[y]) swap(x,y);for(int i=30;i>=0;i--){ //先跳到同一高度 if(dis[f[x][i]]>=dis[y]) x=f[x][i];}if(x==y) return x; //特判 for(int i=30;i>=0;i--){ //一起跳父亲 if(f[x][i]!=f[y][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>s;for(int i=1;i<n;i++){int u,v;cin>>u>>v;a[u].push_back(v);a[v].push_back(u);}dfs(s,0);while(m--){int u,v;cin>>u>>v;cout<<lca(u,v)<<'\n';}
}
/**/

这是我跑的最快的倍增

//May all the beauty be blessed.
#include<bits/stdc++.h>
//#define int long long
using namespace std;
int n,m,s,f[500010][30],d[500010],lg[500010];
vector<int> a[500010];
void dfs(int x,int fa){f[x][0]=fa;d[x]=d[fa]+1;for(int i=1;i<=lg[d[x]];i++) f[x][i]=f[f[x][i-1]][i-1];for(auto i:a[x]) if(i!=fa) dfs(i,x);
}
int lca(int x,int y){if(d[x]<d[y]) swap(x,y);while(d[x]>d[y]) x=f[x][lg[d[x]-d[y]]-1];if(x==y) return x;for(int i=lg[d[x]]-1;i>=0;i--){if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];}return f[x][0];
}
signed main(){ ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m>>s;for(int i=1;i<n;i++){int x,y;cin>>x>>y;a[x].push_back(y);a[y].push_back(x);}for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);dfs(s,0);while(m--){int x,y;cin>>x>>y;cout<<lca(x,y)<<'\n';}
}