根付き木の最小共通祖先 (ダブリング)

概要

根付きの 2 つの頂点の共通の祖先で最も根から遠い位置にあるものを最小共通祖先 (LCA) という．求めるアルゴリズムは色々あるが，ここにはダブリングによるものを載せる．

使い方

lca l(g,r) とすると Graph g の頂点 r を根として前処理をする． l.get(u,v) で LCA を取得．

計算量

前処理 $O(N \log N)$, クエリ $O(\log N)$．

実装

class lca {
public:
    const int n = 0;
    const int log2_n = 0;
    std::vector<std::vector<int>> parent;
    std::vector<int> depth;

    lca() {}

    lca(const Graph &g, int root)
        : n(g.size()), log2_n(log2(n) + 1), parent(log2_n, std::vector<int>(n)), depth(n) {
        dfs(g, root, -1, 0);
        for (int k = 0; k + 1 < log2_n; k++) {
            for (int v = 0; v < (int)g.size(); v++) {
                if (parent[k][v] < 0)
                    parent[k + 1][v] = -1;
                else
                    parent[k + 1][v] = parent[k][parent[k][v]];
            }
        }
    }

    void dfs(const Graph &g, int v, int p, int d) {
        parent[0][v] = p;
        depth[v] = d;
        for (auto &e : g[v]) {
            if (e.dst != p) dfs(g, e.dst, v, d + 1);
        }
    }

    int get(int u, int v) {
        if (depth[u] > depth[v]) std::swap(u, v);
        for (int k = 0; k < log2_n; k++) {
            if ((depth[v] - depth[u]) >> k & 1) {
                v = parent[k][v];
            }
        }
        if (u == v) return u;
        for (int k = log2_n - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
};

検証

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2110335