ホーム > libalgo

根付き木の最小共通祖先 (オイラーツアー)

概要

根付きの 2 つの頂点の共通の祖先で最も根から遠い位置にあるものを最小共通祖先 (LCA) という.オイラーツアーで木を列で表現して RMQ に入れる.

使い方

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

計算量

前処理 $O(N)$, クエリ $O(\log N)$.ダブリング版より僅かに遅い.

実装

class lca {
public:
    int n, segn;
    std::vector<int> path, depth, in_order;
    std::vector<std::pair<int, int>> dat;
    const std::pair<int, int> INF = std::make_pair(1000000000, 1000000000);

    lca(const Graph &g, int root) : n(g.size()), path(n * 2 - 1), depth(n * 2 - 1), in_order(n) {
        int k = 0;
        dfs(g, root, -1, 0, k);
        for (segn = 1; segn < n * 2 - 1; segn <<= 1)
            ;
        dat.assign(segn * 2, INF);
        for (int i = 0; i < (int)depth.size(); ++i) dat[segn + i] = std::make_pair(depth[i], i);
        for (int i = segn - 1; i >= 1; --i) dat[i] = min(dat[i * 2], dat[i * 2 + 1]);
    }

    int get(int u, int v) const {
        int l = std::min(in_order[u], in_order[v]);
        int r = std::max(in_order[u], in_order[v]) + 1;
        return path[range_min(1, segn, l, r).second];
    }

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

    std::pair<int, int> range_min(int v, int w, int l, int r) const {
        if (r <= l || w == 0) return INF;
        if (r - l == w) return dat[v];
        int m = w / 2;
        auto rmin = range_min(v * 2, m, l, std::min(r, m));
        auto lmin = range_min(v * 2 + 1, m, std::max(0, l - m), r - m);
        return min(rmin, lmin);
    }
};

検証

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