【模板】最近公共祖先

xxxasybt2023 · 2025-11-26 20:44:08 · 算法·理论

倍增

struct LCA
{
    static const int N = 5e5+5,M = 1e6+5,P = 20;
    struct node {int to,ne;} edge[M];
    int head[N],len = 0,dep[N],fa[N][P];
    struct iterator
    {
        int indx;LCA *g;
        iterator (int _i,LCA *_g) : indx(_i) , g(_g) {}
        iterator operator++(int) {iterator t = *this;return indx = g->edge[indx].ne,t;}
        int operator*() {return g->edge[indx].to;}
        operator bool () {return (bool)indx;}
    };
    void insert(int u,int v) {edge[++len] = {v,head[u]},head[u] = len;}
    void add(int u,int v) {insert(u,v),insert(v,u);}
    iterator begin(int x) {return iterator(head[x],this);}
    void dfs(int x = 1,int f = 0)
    {
        dep[x] = dep[f]+1,fa[x][0] = f;
        for (int i = 1;i < P;i ++) fa[x][i] = fa[fa[x][i-1]][i-1];
        for (auto i = begin(x);i;i ++) if (*i != f) dfs(*i,x);
    }
    int lca(int x,int y)
    {
        if (dep[x] < dep[y]) swap(x,y);
        for (int i = P-1;i >= 0;i --) if (dep[fa[x][i]] >= dep[y]) x = fa[x][i];
        if (x == y) return x;
        for (int i = P-1;i >= 0;i --) if (fa[x][i] != fa[y][i]) x = fa[x][i],y = fa[y][i];
        return fa[x][0];
    }
};