ST表求LCA

namespace LCA{
    int dfn[N<<1],po[N],dep[N],tot,dfx[N],id,xfd[N];
    il void dfs(int u,int fa){
        dfx[u]=++id,xfd[id]=u;
        dfn[++tot]=dfx[u],dep[u]=dep[fa]+1,po[u]=tot;
        for(ri int i=h[u],v;i;i=e[i].nxt){
            v=e[i].v;
            if(v==fa) continue;
            dfs(v,u),dfn[++tot]=dfx[u];
        }
    }
    int minn[N<<1][25],lg[N<<1];
    il void init(){
        for(ri int i=2;i<=tot;++i) lg[i]=lg[i/2]+1; 
        for(ri int i=1;i<=tot;++i) minn[i][0]=dfn[i];
        for(ri int l=1;l<=25;++l){
            for(ri int i=1;i+(1<<l)<=tot;++i){
                minn[i][l]=min(minn[i][l-1],minn[i+(1<<(l-1))][l-1]);
            }
        }
    }
    il int lca(int s,int t){
        if(po[s]>po[t]) swap(s,t);
        int l_g=lg[po[t]-po[s]+1];
        int fa=min(minn[po[s]][l_g],minn[po[t]-(1<<l_g)+1][l_g]);
        return xfd[fa];
    }
} using namespace LCA;

倍增跳求LCA

namespace LCA{
    int h[N];
    struct qwq{
        int v,nxt;
    }e[N<<1];
    il void add(cs int u,cs int v,cs int i){
        e[i*2-1]={v,h[u]},h[u]=i*2-1;
        e[i<<1]={u,h[v]},h[v]=i<<1;
    }
    int dep[N],f[N][20];
    il void dfs(cs int u){
        dep[u]=dep[f[u][0]]+1;
        for(ri int i=h[u];i;i=e[i].nxt){
            if(e[i].v!=f[u][0]){
                f[e[i].v][0]=u;
                for(ri int l=1;l<20;++l){
                    f[e[i].v][l]=f[f[e[i].v][l-1]][l-1];
                }
                dfs(e[i].v);
            }
        }
        return;
    }
    il int lca(int u,int v){
        if(dep[u]<dep[v]) swap(u,v);
        for(ri int i=19;~i;--i){
            if(dep[f[u][i]]>=dep[v]){
                u=f[u][i];
            }
        }
        if(u==v) return u;
        for(ri int i=19;~i;--i){
            if(f[u][i]!=f[v][i]){
                u=f[u][i],v=f[v][i];
            }
        }
        return f[u][0];
    }
} using namespace LCA;