競プロノート

Appearance

LCA（最小共通祖先） ​

根付き木において、2頂点の共通祖先のうち最も深い頂点を求める。

ダブリングを使い、前処理 O(N log N)、各クエリ O(log N) で求められる。

特徴 ​

項目内容
用途最小共通祖先、木上の距離
前処理O(N log N)
LCAクエリO(log N)
空間計算量O(N log N)

考え方 ​

ダブリングで各頂点の 2^k 個上の祖先を前計算する。

up[k][v] = 頂点vの 2^k 個上の祖先

LCA(a, b) を求める手順：

  1. 深い方の頂点を持ち上げ、深さを揃える。
  2. 2頂点が一致すれば、その頂点がLCA。
  3. 大きな2の累乗から順に、祖先が異なる範囲で両頂点を持ち上げる。
  4. 最後に1つ上の親を返す。

実装 ​

cpp

#pragma once
#include <algorithm>
#include <cassert>
#include <queue>
#include <vector>
using namespace std;

struct LCA {
    int n, lg = 0;
    vector<vector<int>> g, up;
    vector<int> depth;

    LCA(int n) : n(n), g(n) {}

    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    void build(int root = 0) {
        assert(0 <= root && root < n);
        lg = 1;
        while ((1LL << lg) <= n) lg++;
        up.assign(lg, vector<int>(n, root));
        depth.assign(n, -1);

        queue<int> q;
        depth[root] = 0;
        up[0][root] = root;
        q.push(root);
        while (!q.empty()) {
            int v = q.front(); q.pop();
            for (int nv : g[v]) {
                if (depth[nv] != -1) continue;
                depth[nv] = depth[v] + 1;
                up[0][nv] = v;
                q.push(nv);
            }
        }

        for (int j = 1; j < lg; j++) {
            for (int v = 0; v < n; v++) up[j][v] = up[j - 1][up[j - 1][v]];
        }
    }

    // vのk個上の祖先（存在しなければ-1）
    int kth_ancestor(int v, int k) const {
        assert(0 <= v && v < n && depth[v] != -1);
        if (k < 0 || k > depth[v]) return -1;
        for (int j = 0; j < lg; j++) if ((k >> j) & 1) v = up[j][v];
        return v;
    }

    // 最小共通祖先
    int lca(int a, int b) const {
        assert(0 <= a && a < n && 0 <= b && b < n);
        assert(depth[a] != -1 && depth[b] != -1);
        if (depth[a] < depth[b]) swap(a, b);
        a = kth_ancestor(a, depth[a] - depth[b]);
        if (a == b) return a;

        for (int j = lg - 1; j >= 0; j--) {
            if (up[j][a] == up[j][b]) continue;
            a = up[j][a];
            b = up[j][b];
        }
        return up[0][a];
    }

    // 頂点間距離（辺の本数）
    int distance(int a, int b) const {
        int c = lca(a, b);
        return depth[a] + depth[b] - 2 * depth[c];
    }
};

使用例 ​

cpp
LCA lc(7);

lc.add_edge(0, 1);
lc.add_edge(0, 2);
lc.add_edge(1, 3);
lc.add_edge(1, 4);
lc.add_edge(2, 5);
lc.add_edge(2, 6);

lc.build(0);

cout << lc.lca(3, 4) << '\n';      // 1
cout << lc.lca(3, 5) << '\n';      // 0
cout << lc.distance(3, 5) << '\n'; // 4
cout << lc.kth_ancestor(4, 2);    // 0

主な操作 ​

メソッド機能
add_edge(u, v)無向辺を追加
build(root)根を指定して前処理
lca(u, v)最小共通祖先
distance(u, v)頂点間距離（辺数）
kth_ancestor(v, k)k個上の祖先
depth[v]根からの深さ

木上の距離 ​

2頂点 u, v の距離はLCAを用いて求められる。

cpp
int w = lc.lca(u, v);
int d = lc.depth[u] + lc.depth[v] - 2 * lc.depth[w];

注意点 ​

  • 根を指定した木を対象とする。
  • build() を実行してからクエリを呼ぶ。
  • up[k][v] は 2^k 個上の祖先。
  • 根の親は根自身として管理している。
  • 根より上の祖先を kth_ancestor() で要求すると -1 を返す。
  • LCAは根の選び方によって変わる。
  • distance() は根の選び方に依存しない。
  • 現在の実装の距離は辺数。重み付き木なら根からの距離を別途管理する。
  • 非連結グラフや一般グラフをそのまま入力する用途には対応していない。

関連 ​