Latest Common Ancestor

概要

木構造における任意の2ノードの最近共通祖先を 1 クエリ当たり O(logN) で求めるためのデータ構造。 最近共通祖先については下記を参照。

ダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）を求めるアルゴリズム | アルゴリズムロジック

最近木においてある頂点の祖先は「親をたどってたどり着ける頂点」を指し、2頂点の共通祖先は「2頂点が共通して持つ祖先」のことを言います。 頂点 u と v の最近共通祖先(LCA:...

algo-logic.info

method

• init(Graph, root : option) : 隣接リストのグラフから、最近共通祖先を求めるにあたって必要なダブリングの前計算を行う
• query(u, v) : 二つのノード u, v の最近共通祖先を O(logN) で求める

Program

struct Edge {
    ll to;
};
using Graph = vector<vector<Edge>>;
struct LCA {
    vector<vector<int>> parent;
    vector<int> dist;
    LCA(const Graph &G, int root = 0) { init(G, root); }
    // 初期化
    void init(const Graph &G, int root = 0) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++;
        //parent[i][j] : 2^i先の親
        parent.assign(K, vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; 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;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e.to != p) dfs(G, e.to, v, d + 1);
        }
    }
    int query(int u, int v) {
        if (dist[u] < dist[v]) swap(u, v);
        int K = parent.size();
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
};