【模板】最近公共祖先（LCA）

posted on 2021-08-04 14:22:40 | under 学术 | source

LCA，Least Common Ancestors，最近公共祖先。

倍增。

首先预处理出数组 \(d_i\) 和 \(f_{i,j}\)。

• \(d_i\) 表示第 \(i\) 个节点的深度。
  转移方程：\(d_{i}=d_{\text{fa}}+1\)
• \(f_{i,j}\) 表示第 \(i\) 个节点的第 \(2^j\) 级祖先。
  转移方程：\(f_{i,0}=\text{fa},f_{i,j}=f_{f_{i,j-1},j-1}\)

接着是 LCA。分成以下几个步骤：

1. 把 \(x,y\) 跳到同一层。
2. 使用倍增思想把 \(x,y\) 跳到离 LCA 最近的节点。
3. 最终 \(f_{x,0}\) 或 \(f_{y,0}\) 为 \(x,y\) 的 LCA。

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
template<int N,int M> struct Graph{
    int cnt,head[N+10];
    struct Edge{
        int s,e,w,nxt;
        Edge(int s=0,int e=0,int w=0,int nxt=0):
            s(s),e(e),w(w),nxt(nxt){}
    } a[(M<<1)+10];
    Graph():cnt(0){memset(head,0,sizeof head);}
    void add(int s,int e,int w=0){a[++cnt]=Edge(s,e,w,head[s]),head[s]=cnt;}
    void link(int s,int e,int w=0){add(s,e,w),add(e,s,w);}
};
template<int N> struct Math{
    int lg[N+10];
    Math(){
        lg[0]=-1;
        for(int i=1;i<=N;i++) lg[i]=lg[i>>1]+1;
    }
    int log(int x){return lg[x];}
    int pow(int x){return 1<<x;}
};
int n,m;
Graph<500010,500010> g;
Math<5000010> math;
int f[500010][21],d[500010];
void dfs(int root,int fa){
    f[root][0]=fa,d[root]=d[fa]+1;
    for(int i=1;i<=math.log(d[root]);i++){
        f[root][i]=f[f[root][i-1]][i-1];
    }
    for(int i=g.head[root];i;i=g.a[i].nxt){
        int to=g.a[i].e;
        if(to!=fa) dfs(to,root);
    }
}
int lca(int x,int y){
    if(d[x]<d[y]) swap(x,y);
    int jmp=d[x]-d[y];
    for(int i=math.log(jmp);i>=0;i--){
        if((jmp>>i)&1) x=f[x][i];
    }
    if(x==y) return x;
    for(int i=math.log(n);i>=0;i--){
        if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
    }
    return f[x][0];
}
int root;
int main(){
    cin>>n>>m>>root;
    for(int i=1;i<=n-1;i++){int x,y;
        cin>>x>>y;
        g.link(x,y);
    }
    dfs(root,root);
    for(int i=1;i<=m;i++){int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
    return 0;
}