ダブリングによる木の最近共通祖先(LCA:Lowest Common Ancestor)を求めるアルゴリズム

2020年3月16日グラフ,競プロ,LCA,ダブリング,木の2頂点間の距離,木のパス上に頂点があるか

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

頂点 u と v の最近共通祖先(LCA: Lowest Common Ancestor) とは、「共通祖先の中でも、最も u, v に近い頂点」のことです。

頂点0 を根とする木。頂点 4 と頂点 6 の LCA は頂点 1

アルゴリズム

ダブリングによりLCAを求めるアルゴリズム:

  • 前処理
    1. DFSなどによって、全ての頂点について、根からの距離と親を求める
    2. ダブリングによって \(2^k\) 先の祖先を求める
  • クエリ(u と v の最近共通祖先 x を求める。)
    1. u と v の深い方の頂点を変更して「x までの距離が同じ点 u1, v1」にする
    2. 二分探索を用いて u1, v1 を最近共通祖先 x の一つ手前まで段階的に移動させる(u1, v1 が同じにならないギリギリまで移動させる)
    3. 最終的な u1, v1 の一つ先が LCA

※ x から先の頂点は全て「共通祖先」となるため二分探索が使用できますが、普通の二分探索のように、「dを決め打ちして、d先の頂点を実際に得ようとする」のは一回あたり\(O(logN)\)かかり、全体で\(O((logN)^2)\)の計算量になります。(つまり「条件 C(d):u1 と v1 から d さかのぼった点は共通祖先か」を満たす最小の d を二分探索で見つけるような場合です。)
ですが \(k = 2^K, 2^{(K-1)}, 2^{(K-2)},… , 2^0\) について 「k個先を確認して共通祖先でないなら u1,v1 をk個先に移動」ということを繰り返すと、最終的に u1,v1 が LCA の直前になるまで移動させることができ、全体で\(O(logN)\)で求めることが可能です。

以上の話は実装例を見たほうが早いかもしれません。


※ u1, v1 の片方は、もともとの u, v と同じ頂点です。

u の方が v よりも深い
u の方が深いので、同じ高さになるように変更する

※ダブリングについては、ダブリングの基本概念とその応用 を参照してください

計算量

  • 前処理:\(O(N\log N)\) 時間, \(O(N \log N)\) 空間
  • クエリ:\(O(\log N)\)

N 頂点あった時、一つの頂点あたり約 \(\log N\) 個の値を保持する必要があります。よって、時間計算量・区間計算量ともに \(O(N \log N)\) です。

C++ による実装例とまとめ

グラフ G と根 root を受け取って前処理を行い、LCA を二分探索で求めます。

struct Edge {
    long long to;
};
using Graph = vector<vector<Edge>>;

/* LCA(G, root): 木 G に対する根を root として Lowest Common Ancestor を求める構造体
    query(u,v): u と v の LCA を求める。計算量 O(logn)
    前処理: O(nlogn)時間, O(nlogn)空間
*/
struct LCA {
    vector<vector<int>> parent;  // parent[k][u]:= u の 2^k 先の親
    vector<int> dist;            // root からの距離
    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.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]];
                }
            }
        }
    }

    // 根からの距離と1つ先の頂点を求める
    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);  // u の方が深いとする
        int K = parent.size();
        // LCA までの距離を同じにする
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        // 二分探索で LCA を求める
        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];
    }
};

アルゴリズムの説明

ダブリングとは

ダブリングは全体の要素数がN個のとき「K個先の要素を求めるのに \(O(K)\) かかる」ような状況を

  • 前処理:\(O(N \log K)\) 時間, \(O(N \log K)\) 空間
  • クエリ:\(O(\log K)\)

で行うことができるようにするアルゴリズムです。

実現のためには以下のようにします。

  • 前処理
    1. それぞれの要素について 1 個先の要素が何か記録
    2. 前の結果を利用して、それぞれの要素について 2 個先の要素が何か記録
    3. 前の結果を利用して、それぞれの要素について 4 個先の要素が何か記録
    4. 前の結果を利用して、それぞれの要素について 8 個先の要素が何か記録
    5. 前の結果を利用して、それぞれの要素について 16 個先の要素が何か記録
  • クエリ:二分探索や繰り返し二乗法と同様の方法で K 個先の要素が何か探索

\(2^k\) 先の要素が分かっていれば「 “\(2^k\) 先の要素" の\(2^k\) 先」を簡単に求めることができるので、「\(2^{k+1}\) 先の要素が何か」を高速に求めることができます。

LCAをダブリング求めるアイディア

根から頂点 v への距離を dist(v) と書くことにします。頂点 u, v の LCA が x だった場合、以下が成り立つはずです。

  • u から dist(u)-dist(x) 回 だけ根へさかのぼった時の点が x
  • v から dist(v)-dist(x) 回 だけ根へさかのぼった時の点が x

このままではダブリングが使えません。そこで以下のように「x までの距離が同じ点 u1, v1」を用意します。簡単のために u の方がより深い点としましょう。つまり dist(u)>dist(v) です。

  • u から |dist(u)-dist(v)| 回 さかのぼった点を u1 とする
    • u1 から「 dist(v) – dist(x) 」回さかのぼった点が x
  • v を v1 とする
    • v1 から 「dist(v) – dist(x)」 回さかのぼった点が x
x までの距離は同じ

こうすると、「u1 と v1 からある距離(dist(v) – dist(x))以上の距離 d だけさかのぼると同じ頂点になる」と言えます(最近共通祖先から先の祖先は全て共通祖先です)。

このようにすると、二分探索を利用することができて、二分探索を用いて u1, v1 を最近共通祖先 x の一つ手前まで段階的に移動させる(u1, v1 が同じにならないギリギリまで移動させる)ようにすれば良いです。

応用

LCA で 任意の2頂点間の距離が分かる

LCA の計算過程で、根からの距離を全ての頂点について計算済みです。

頂点 u, v の LCA が x だった場合、

  • dist(u) + dist(v) – 2 × dist(x)

で u, v 間の距離を求めることができます。

int get_dist(int u, int v) { return dist[u] + dist[v] - 2 * dist[query(u, v)]; }

パス上にある頂点があるか分かる

頂点 u, v を結ぶパス上に、ある頂点 a が存在するかも簡単に判定ができます。

頂点 a がパス上にあれば

  • u と a の距離 + a と v の距離
  • u と v の距離

が等しくなります。逆に等しくなければパス上にはありません。

bool is_on_path(int u, int v, int a) { return get_dist(u, a) + get_dist(a, v) == get_dist(u, v); }

練習問題