Lowest Common Ancestor

LCA.cpp

struct LCA {
    typedef vector<vector<int>> Graph;
    Graph G;
    vector<int> depth;
    vector<vector<int>> parent;
    int n, root, MAXLOG;
 
    LCA(int _n) {
        root = 0;
        n = _n;
        MAXLOG = (int)log2(_n) + 1;
        G.assign(_n, vector<int>());
        depth.assign(_n, 0);
        parent.assign(MAXLOG + 1, vector<int>(_n, 0));
    }
 
    void dfs(int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for(auto&& dst : G[v]) {
            if(dst != p) dfs(dst, v, d + 1);
        }
    }
 
    void init(int root = 0) {
        dfs(root, -1, 0);
        for(int k = 0; k + 1 < MAXLOG; k++) {
            for(int v = 0; v < n; v++) {
                if(parent[k][v] < 0) parent[k + 1][v] = -1;
                else parent[k + 1][v] = parent[k][parent[k][v]];
            }
        }
    }
 
    int lca(int u, int v) {
        if(depth[u] > depth[v]) swap(u, v);
        for(int k = 0; k < MAXLOG; k++) {
            if((depth[v] - depth[u]) >> k & 1) v = parent[k][v];
        }
        if(u == v) return u;
        for(int k = MAXLOG - 1; k >= 0; k--) {
            if(parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
 
    void add_edge(int a, int b) {
        G[a].emplace_back(b);
        G[b].emplace_back(a);
    }
};