【算法学习笔记】倍增求最近公共祖先（LCA，非战斗机）

2023-08-06 08:12:40

\(0.\) 问题简介

有一棵树，告诉你它的节点数n，根的编号s以及所有的边。求m次询问，每次查询给定任意两个树上节点的最近公共祖先。

数据范围：\(n,m\leq 10^5\)

\(1.\) 暴力

暴力很好理解，就是一个一个往他的父亲节点跳。学过并查集的同学们应该都知道，一个一个往上跳这种做法是很浪费时间的，所以针对这道题，也会\(tle\)

\(2.\) 优化（倍增）

~~看标题也都会知道一定是倍增~~

针对并查集，我们采取的优化办法是路径压缩求解。但很明显，\(LCA\)要求的是当前节点到根的路径上的某个信息，每次查询还有可能不同。

所以这种办法对于\(LCA\)问题不可行。

让后便有了以下名言

出题人说：“数据要大！”

于是便有了倍增。

关于倍增，在“RMQ问题与ST表”这篇博客中有初步介绍。

对于这种问题，我们可以事先统计出每个节点第\(2^k\ (k\in N_+)\)辈父亲节点，然后便可以大大减少时间。

统计树上信息（\(dfs\)）

（个人认为\(dfs\)比较容易理解且代码简洁）

首先引入一个重要的定义：\(fa\)数组

其中：\(fa_{i,j}\)代表第\(i\)号结点第\(2^j\)辈祖先

所以可得
\[ fa_{i,j}=fa_{fa_{i,j-1},j-1}\]

这样，我们就可以方便地得到\(fa_{i,j}\)

inline void dfs(int now,int pre){//now为当前节点，pre为其直接父亲节点，也就是上一个被搜到的节点
    fa[now][0]=pre;
    depth[now]=depth[pre]+1;//记录深度
    for(rg int i=1;i<=lg[depth[now]];i++) fa[now][i]=fa[fa[now][i-1]][i-1];//刚才的式子
    for(rg int i=head[now];i;i=nxt[i]){
    if(edge[i]!=pre) dfs(edge[i],now);//遍历所有连接子节点（非父亲节点）的边，递归下一层
    }
}

求解\(LCA\)

讲解都在代码注释里了，直接贴代码吧

inline int lca(int x,int y){
    if(depth[x]<depth[y]) swap(x,y);//首先保证x的深度要大于y，便于操作
    while(depth[x]>depth[y]) x=fa[x][lg[depth[x]-depth[y]]-1];//将x调到和y同层，便于同时向上跳，这里也用到了倍增
    if(x==y) return x;//如果x恰好与y相同，则证明x与y的LCA就是x
    for(rg 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];//跳到最后的x节点的父亲节点就是LCA，返回
}

完整代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath> 

using namespace std;

#define rg register
#define ll long long
#define ull unsigned long long

namespace Enterprise{
    inline int read(){
        rg int s=0,f=0;
        rg char ch=getchar();
        while(not isdigit(ch)) f|=(ch=='-'),ch=getchar();
        while(isdigit(ch)) s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
        return f?-s:s;
    }
    
    const int N=5e5+15;
    int head[N],edge[N<<1],nxt[N<<1],tot;
    int depth[N],fa[N][25],lg[N],n,m,s;
    
    inline void add(int u,int v){
        edge[++tot]=v;
        nxt[tot]=head[u];
        head[u]=tot;
    }
    
    inline void dfs(int now,int pre){
        fa[now][0]=pre;
        depth[now]=depth[pre]+1;
        for(rg int i=1;i<=lg[depth[now]];++i) fa[now][i]=fa[fa[now][i-1]][i-1];
        for(rg int i=head[now];i;i=nxt[i]){
            if(edge[i]!=pre) dfs(edge[i],now);
        }
    }
    
    inline 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(rg 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];
    }
    
    inline void main(){
        n=read(),m=read(),s=read();
        for(rg int i=1;i<n;i++){
            int u=read(),v=read();
            add(u,v);
            add(v,u);
        }
        
        for(rg int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);
        
        dfs(s,0);
        
        for(rg int i=1;i<=m;i++){
            int x=read(),y=read();
            printf("%d\n",lca(x,y));
        }

    }
}

signed main(){
    Enterprise::main();
    return 0;
}

\(3.\)后记

关于代码中如下一段，做一下说明

for(rg int i=1;i<=n;i++) lg[i]=lg[i-1]+(1<<lg[i-1]==i);

这是对于求解\(log_2n\)的优化，可以手推一下，手推不出直接背过也可。

码农公寓