ST表lca

hubingshan · 2023-11-03 12:04:40 · 个人记录

struct Lca{
    int tot=0;
    int dep[N],pos[N],lca[N*2][20],lg[N*2];
    void pre(int x,int fa){
        dep[x]=dep[fa]+1,pos[x]=++tot,lca[tot][0]=x;
        for(int i=h[x];i;i=d[i].n){
            int y=d[i].b;
            if(y==fa) continue;
            pre(y,x);lca[++tot][0]=x;
        }
    }
    int xiao(int x,int y){
        if(dep[x]<dep[y]) return x;
        return y;
    }
    void ST(){
        lg[0]=-1;
        for(int i=1;i<=tot;i++) lg[i]=lg[i/2]+1;
        for(int j=1;j<=19;j++){
            for(int i=1;i+(1<<j)-1<=tot;i++) lca[i][j]=xiao(lca[i][j-1],lca[i+(1<<(j-1))][j-1]);
        }
    }
    int LCA(int x,int y){
        if(pos[x]>pos[y]) swap(x,y);
        int len=pos[y]-pos[x]+1;
        return xiao(lca[pos[x]][lg[len]],lca[pos[y]-(1<<lg[len])+1][lg[len]]);
    }   
    int dis(int x,int y){
        int _lca=LCA(x,y);
        return dep[x]+dep[y]-2*dep[_lca];
    }
}Tl;