LCA 详解

全栈程序员-站长 • 2026年3月19日上午11:19 • 未分类 • 阅读 3

LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科

LCA

比如在上面这幅图当中：
( LCA(A,B) —- 表示A,B的最近公共祖先。)

相信你应该理解,LCA,是什么了吧，那么怎么求LCA呢？

这里我们有两种在线的算法：

暴力
倍增

暴力虽然可以计算，但是碰到数据大的题目，肯定会被 T 到飞起。

所以一般在线计算LCA我们一般使用倍增（离线可以tarjan）。

所谓倍增，就是按2的倍数来增大，也就是跳 1,2,4,8,16,32 …… 不过在这我们不是按从小到大跳，而是从大向小跳，即按……32,16,8,4,2,1来跳，如果大的跳不过去，再把它调小。

首先我们使用链式前向星存树。

然后我们令 f[i][j] 表示 i 节点的 2^j 级祖先。

于是我们可以dfs一遍，找到每个节点的所有 2次幂的祖先。

代码：

// h[x] 为 x节点得到深度 f[i][j]与上面一样 // void dfs(int x,int fa){ 
     h[x]=h[fa]+1; f[x][0]=fa; for(int i=1;(1<<i)<=h[x];i++) f[x][i]=f[f[x][i-1]][i-1];//意思是f的2^i祖先等于f的2^(i-1)祖先的2^(i-1)祖先 for(int i=head[x];i;i=nex[i]){ 
     if(to[i]!=fa) dfs(to[i],x); } }

然后就是具体求LCA了：

我们先把两个点提到同一高度，再统一开始跳。但我们在跳的时候不能直接跳到它们的LCA，因为这可能会误判，比如10和11，在跳的时候，我们可能会认为7是它们的LCA，但7只是它们的祖先，它们的LCA其实是9。所以我们要跳到它们LCA的下面一层，然后输出它们的父节点，这样就不会误判了。

做之前，我们可以预处理一下 log 的值，这样跑得更快

for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i); //预处理出log2(i)+1

代码：

int LCA(int x,int y){ 
     if(h[x]<h[y]) swap(x,y);//假设x是最深的节点 while(h[x]>h[y]) x=f[x][lg[h[x]-h[y]]-1];//让两个节点一样深 if(x==y) return x; for(int i=lg[h[x]]-1;i>=0;i--) if(f[x][i]!=f[y][i])//如果不一样那么肯定没有到达lca ，因为两个节点的lca 向上的节点就是一样的了 x=f[x][i],y=f[y][i]; return f[x][0]; }

最后总代码：

#include 
      using namespace std; const int N=5e5+10; int head[N],nex[N<<1],to[N<<1],tot; int n,m,s,f[N][30],lg[N],h[N]; void add(int a,int b){ 
     to[++tot]=b; nex[tot]=head[a]; head[a]=tot; } void dfs(int x,int fa){ 
     h[x]=h[fa]+1; f[x][0]=fa; for(int i=1;(1<<i)<=h[x];i++) f[x][i]=f[f[x][i-1]][i-1]; for(int i=head[x];i;i=nex[i]){ 
     if(to[i]!=fa) dfs(to[i],x); } } int LCA(int x,int y){ 
     if(h[x]<h[y]) swap(x,y); while(h[x]>h[y]) x=f[x][lg[h[x]-h[y]]-1]; if(x==y) return x; for(int i=lg[h[x]]-1;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int main(){ 
     scanf("%d %d %d",&n,&m,&s); for(int i=1;i<n;i++){ 
     int x,y; scanf("%d %d",&x,&y); add(x,y); add(y,x); } dfs(s,0); for(int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i); while(m--){ 
     int a,b; scanf("%d %d",&a,&b); printf("%d\n",LCA(a,b)); } return 0; }