最近公共祖先LCA

luckydrawbox · 2022-09-03 22:56:27 · 个人记录

倍增法

变量

函数

代码

struct LCA{
    int fa[N][LOGN],dep[N];
    int lg[N];
    LCA(){
        lg[0]=0;
        for(int i=1;i<N;i++)
            lg[i]=lg[i-1]+(1<<lg[i-1]==i);
    }
    void dfs(int x,int f){
        fa[x][0]=f;
        dep[x]=dep[f]+1;
        for(int i=1;i<=lg[dep[x]];i++)
            fa[x][i]=fa[fa[x][i-1]][i-1];
        for(int i=G.head[x];i;i=G.nxt[i])
            if(G.ver[i]!=f)
                dfs(G.ver[i],x);
    }
    void init(int root){
        dfs(root,0);
    }
    int ask(int u,int v){
        if(dep[u]<dep[v])
            swap(u,v);
        while(dep[u]>dep[v])
            u=fa[u][lg[dep[u]-dep[v]]-1];
        if(u==v)
            return u;
        for(int i=lg[dep[u]]-1;i>=0;i--)
            if(fa[u][i]!=fa[v][i]){
                u=fa[u][i];
                v=fa[v][i];
            }
        return fa[u][0];
    }
}tree;

Tarjan法

变量

函数

代码

struct LCA{
    int v[N],lca[N];
    int fa[N];
    vector<int> que[N],qid[N];
    void init(int n){
        memset(v,0,sizeof(v));
        memset(lca,0,sizeof(lca));
        for(int i=1;i<=n;i++)
            fa[i]=i;
        for(int i=1;i<=n;i++){
            que[i].clear();
            qid[i].clear();
        }
    }
    void add_query(int x,int y,int id){
        if(x==y){
            lca[id]=x;
            return;
        }
        que[x].push_back(y);
        qid[x].push_back(id);
        que[y].push_back(x);
        qid[y].push_back(id);
    }
    int get(int x){
        if(x==fa[x])
            return x;
        return fa[x]=get(fa[x]);
    }
    void tarjan(int x){
        v[x]=1;
        for(int i=G.head[x];i;i=G.nxt[i]){
            int y=G.ver[i];
            if(v[y])
                continue;
            tarjan(y);
            fa[y]=x;
        }
        for(int i=0;i<que[x].size();i++){
            int y=que[x][i],id=qid[x][i];
            if(v[y]==2)
                lca[id]=get(y);
        }
        v[x]=2;
    }
    void solve(int root){
        tarjan(root);
    }
};