LCA 各种模板

LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点u和v最近的公共祖先。 ———来自百度百科

倍增LCA

预处理复杂度$O(nlogn)$,查询复杂度$O(logn)$

struct node {
    int v,next;
} e[N];

int n,m;
int cnt,head[N],dep[N],fa[N][22],lg[N];

void add(int u,int v) {
    e[++cnt].v=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}

void init(){
    for(int i=1; i<=n; i++)
        lg[i]=lg[i-1]+((1<<lg[i-1])==i);
}

void dfs(int u,int f) {
    fa[u][0]=f;
    dep[u]=dep[f]+1;
    for(int i=1; i<=lg[dep[u]]; i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=head[u]; i; i=e[i].next)
        if(e[i].v!=f) dfs(e[i].v,u);
}

int lca(int x,int y) {
    if(dep[x]<dep[y]) swap(x,y);
    while(dep[x]>dep[y]) x=fa[x][lg[dep[x]-dep[y]]-1];
    if(x==y) return x;
    for(int k=lg[dep[x]]-1; k>=0; k--)
        if(fa[x][k]!=fa[y][k]) x=fa[x][k],y=fa[y][k];
    return fa[x][0];

}

树剖LCA

预处理复杂度$O(n)$，查询复杂度$O(logn)$

vector<int>e[N];
int fa[N],dep[N],son[N],siz[N],top[N];

void dfs1(int u,int f) {
    fa[u]=f;
    dep[u]=dep[f]+1;
    siz[u]=1;
    for(auto v:e[u]) {
        if(v==f)continue;
        dfs1(v,u);
        siz[u]+=siz[v];
        if(siz[v]>siz[son[u]]) son[u] = v; 
    }
}

void dfs2(int u,int t) {
    top[u]=t;
    if(!son[u]) return ;
    dfs2(son[u],t);
    for(auto v:e[u]) {
        if(v==son[u]||v==fa[u])
            continue;
        dfs2(v,v);
    }
}

int lca(int x,int y) {
    while(top[x]!=top[y]) {
        if(dep[top[x]]<dep[top[y]])    swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]>dep[y]?y:x;
}

欧拉序LCA

预处理复杂度$O(nlogn)$，查询复杂度$O(1)$

struct Grand_Father {
    int deep[N], euler[N << 1], esiz, rid[N],log_2[N<<1];
    void dfs(int u, int fa) {
        deep[u] = deep[fa] + 1;
        rid[u] = esiz + 1;
        for(auto v:e[u]) {
            if(v == fa) continue;
            euler[++esiz] = u;
            dfs(v, u);
        }
        euler[++esiz] = u;
    }
    int mn[N << 1][23];

    inline void rmq_init() {
        if(!log_2[2]) for(int i=2; i<N*2; i++) log_2[i] = log_2[i >> 1] + 1;
        for(int i=1; i<=esiz; i++) mn[i][0] = euler[i];
        for(int j=1; (1 << j) <= esiz; j++) {
            for(int i=1; i + (1 << j) - 1 <= esiz; i++) {
                if(deep[mn[i][j - 1]] < deep[mn[i + (1 << (j - 1))][j - 1]]) mn[i][j] = mn[i][j - 1];
                else mn[i][j] = mn[i + (1 << (j - 1))][j - 1];
            }
        }
    }
    void solve(int s) {
        esiz = 0;
        dfs(s, 0);
        rmq_init();
    }
    inline int rmq(int l, int r) {
        int det = r - l + 1, kk = log_2[det];
        if(deep[mn[l][kk]] <= deep[mn[r - (1 << kk) + 1][kk]]) return mn[l][kk];
        else return mn[r - (1 << kk) + 1][kk];
    }
    inline int lca(int u, int v) {
        int l = rid[u], r = rid[v];
        if(l > r) swap(l, r);
        return rmq(l, r);
    }
    inline int dis(int u, int v) {
        return deep[u] + deep[v] - 2 * deep[lca(u,v)];
    }
} LCA;