← all categories

Lca Binary Lifting 3615c86b

Lowest common ancestor via Euler tour (tin/tout) + binary lifting. Recursive Euler tour; may need a larger stack for very deep/skewed trees.

Time: O(n \log n) build, O(\log n) per query. tested

content/graphs/lca-binary-lifting.h

struct LCA {
    int timer = 0, n, LOGN;
    vector<int> tin, tout;
    vector<vector<int>> up;

    LCA(int n, vector<vector<int>> &adj, int root = 0) : n(n) {
        LOGN = n > 1 ? (int)ceil(log2(n)) : 1;
        tin.resize(n);
        tout.resize(n);
        up.assign(n, vector<int>(LOGN + 1));
        dfs(root, root, adj);
    }

    void dfs(int u, int p, vector<vector<int>> &adj) {
        tin[u] = timer++;
        up[u][0] = p;
        for (int i = 1; i <= LOGN; i++) up[u][i] = up[up[u][i - 1]][i - 1];
        for (int v : adj[u]) if (v != p) dfs(v, u, adj);
        tout[u] = timer - 1;
    }

    bool isAncestor(int u, int v) { return tin[u] <= tin[v] && tout[v] <= tout[u]; }

    int lca(int u, int v) {
        if (isAncestor(u, v)) return u;
        if (isAncestor(v, u)) return v;
        for (int i = LOGN; i >= 0; i--)
            if (!isAncestor(up[u][i], v)) u = up[u][i];
        return up[u][0];
    }
};