最近公共祖先(LCA)详解

创作时间:

作者:

@小白创作中心

最近公共祖先(LCA)详解

引用

CSDN

https://blog.csdn.net/m0_74732859/article/details/138141794

最近公共祖先（Lowest Common Ancestor, LCA）是树结构中的一个重要概念，广泛应用于各种算法问题中。本文将详细介绍LCA的三种经典解法：向上标记法、树上倍增法和Tarjan离线算法。通过本文的学习，读者将能够掌握LCA问题的求解思路和具体实现方法。

1.前言

公共祖先问题是指在一个树结构中，找到两个节点的最近公共祖先（Lowest Common Ancestor, LCA）。公共祖先指的是两个节点的某个祖先节点，而最近公共祖先则指的是离这两个节点最近的共同的祖先节点。

2.向上标记法

基本思想：

假如要你求出p 和q 的最近公共祖先，我们可以先让p 不断向上遍历，同时标记过已经走过的地方，遍历到树根时停止，然后再让q 向上遍历，如果遇到了被标记的地方，那么这个节点就是p 和q 的最近公共祖先。

向上标记法时间复杂度为O(n)，一般情况下不常用，故不再细讲。

3.树上倍增法

基本思想：

所谓树上倍增法其实就是每次跳跃时按照2的倍数进行跳跃，但我们每次跳跃是按照倍数递减的步数去跳跃的（这个下面会接着讲解），然后我们就可以以log(n)的复杂度查询完整个过程。

对于倍增法的具体实现，我们首先需要处理出一个数组fa，这个数组的作用记录每个节点的2^i级祖先，方便后续查找，顺手我们可以处理出每个节点的深度，实现过程如下：

预处理深搜代码：

void dfs(int f,int father)
{
    fa[f][0]=father;
    depth[f]=depth[father]+1;
    
    for(int i=1;i<lg[depth[f]];i++)
        fa[f][i]=fa[fa[f][i-1]][i-1]; //这一步一定一定要认真手推一下
                         //我们惊奇的刚好可以发现到达的地方是f的2^i-1的2^i-1级祖先
    for(int i=0;i<v[f].size();i++)
        if(v[f][i]!=father)
        dfs(v[f][i],f);
}

预处理lg数组求出log(i)+1 ：

for(int i=1;i<=n;i++)
    lg[i]=lg[i-1]+(1<<lg[i-1]==i);
        //这里预处理很关键，可以快速得出log(i)+1的值，看不懂的一定要手推

然后我们预处理结束后，下一步假如x和y节点深度不同，我们先让x和y先往上跳到同一深度处，如果还不相同，然后再倍增同步向上跳到最近公共祖先处。

int LCA(int x,int y)
{
    if(depth[x]<depth[y])
        swap(x,y);
    while(depth[x]>depth[y])
        x=fa[x][lg[depth[x]-depth[y]]-1];//先一起跳到同一深度处
        
    if(x==y)
        return x;
    
    for(int k=lg[depth[x]]-1;k>=0;k--)
        if(fa[x][k]!=fa[y][k])  //最后一步跳也很关键，如果说跳的地方不相等，
        x=fa[x][k],y=fa[y][k];  //说明结果还在下一层，还要接着跳，不理解的一定要手推
    
    return fa[x][0];
}

奉上完整代码：

#include <bits/stdc++.h>
 
using namespace std;
typedef long long LL;
const int N=5e5+10;
vector<int> v[N];
int depth[N];
int fa[N][30];
int lg[N];
void dfs(int f,int father)
{
    depth[f]=depth[father]+1;
    fa[f][0]=father;
    
    for(int i=1;i<lg[depth[f]];i++)
        fa[f][i]=fa[fa[f][i-1]][i-1];
    
    for(int i=0;i<v[f].size();i++)
        if(v[f][i]!=father)
        dfs(v[f][i],f);
}
int LCA(int x,int y)
{
    if(depth[x]<depth[y])
        swap(x,y);
    while(depth[x]>depth[y])
        x=fa[x][lg[depth[x]-depth[y]]-1];
        
    if(x==y)
        return x;
    
    for(int k=lg[depth[x]]-1;k>=0;k--)
        if(fa[x][k]!=fa[y][k])
        x=fa[x][k],y=fa[y][k];
    
    return fa[x][0];
}
int main()
{
    int n,m,s;
    cin>>n>>m>>s;
    
    for(int i=0;i<n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);  
        v[y].push_back(x);
    }
    
    for(int i=1;i<=n;i++)
        lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    
    dfs(s,0);
    
    for(int i=1; i<=m; i++) 
    {
        int x,y; 
        scanf("%d%d",&x,&y);
        cout<<LCA(x,y)<<endl;
    }
    
    return 0;
}

4.Tarjan(LCA)离线求法

基本思想：

tarjan离线求法主要思想其实是并查集的思想，也就是先把所有询问存起来，先不进行处理
然后逐步深搜，遍历a的所有邻接点，初始化并查集
最后如果a的所有邻接点都被搜过，这是我们再处理所有和a有关的询问，如果b也被搜过，那么就使用并查集搜索a和b的最近公共祖先。

奉上代码：

#include <bits/stdc++.h>
 
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=5e5+10;
vector<int> v[N];
vector<PII> query[N];
int res[N],p[N];
bool f[N];
int find(int u)
{
    if(p[u]!=u)
    p[u]=find(p[u]);
    return p[u];
}
void tarjan(int u)
{
    f[u]=true;
    for(int i=0;i<v[u].size();i++)
    {
        int g=v[u][i];
        if(!f[g])
        {
            tarjan(g);
            p[g]=u;
        }
    }
    
    for(int i=0;i<query[u].size();i++)
    {
        int g=query[u][i].first,j=query[u][i].second;
        if(f[g])
        res[j]=find(g);
    }
}
int main()
{
    int n,m,s;
    cin>>n>>m>>s;
    
    for(int i=0;i<n-1;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    
    for(int i=1;i<=m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        query[a].push_back({b,i});
        query[b].push_back({a,i});
    }
    
    for(int i=1;i<=n;i++)
    p[i]=i;
    tarjan(s);
    
    for(int i=1;i<=m;i++)
    cout<<res[i]<<endl;
    
    return 0;
}