LCA算法详解

使用链式前向星。

DFS函数处理某个点第2ⁱ的父亲关系。

lca函数中不要忘了拉平(将a,b点拉至同一深度)最后用倍增算法找父亲。

log₂的预处理直接使用 log2() 函数即可。

链式前向星的道路数组要开2倍。

#include<bits/stdc++.h>
using namespace std;
int N,M,S;
struct edge{
    int t,nx;
} r[500002<<1];
int rf[500002],rcnt;
void add(int a,int b){//链式前向星
    rcnt++;
    r[rcnt].t=b;
    r[rcnt].nx=rf[a];
    rf[a]=rcnt;
    return;
}
int lg[500002],depth[500002],fa[500002][22];
void dfs(int now,int fat){//找2^i次方的fa  now现在所在的节点 fat该节点的fa
    fa[now][0]=fat;
    depth[now]=depth[fat]+1;
    for(int i=1;i<=lg[depth[now]];i++){
        fa[now][i]=fa[fa[now][i-1]][i-1];
    }
    int cnt=rf[now];
    while(cnt>0){
        if(r[cnt].t!=fat) dfs(r[cnt].t,now);
        cnt=r[cnt].nx;
    }
    return;
}
int lca(int a,int b){
    if(depth[a]<depth[b]){
        swap(a,b);
    }
    while(depth[a]>depth[b]){
        a=fa[a][lg[depth[a]-depth[b]]];
    }
    if(a==b){
        return a;
    }
    for(int i=lg[depth[a]];i>=0;i--){
        if(fa[a][i]!=fa[b][i]){
            a=fa[a][i];
            b=fa[b][i];
        }
    }
    return fa[a][0];
}
int main(){
    // freopen("1in","r",stdin);
    // freopen("1out","w",stdout);
    cin>>N>>M>>S;
    for(int i=1;i<N;i++){
        int x,y;
        cin>>x>>y;
        add(x,y);
        add(y,x);
    }

    for(int i=1;i<=N;i++){
        lg[i]=log2(i);
    }

    dfs(S,0);

    for(int i=1;i<=M;i++){
        int x,y;
        cin>>x>>y;
        cout<<lca(x,y)<<endl;
    }
    return 0;
}