最小共通祖先 (Lowest Common Ancestor, LCA)

概要

根付き木\(T\)のある頂点\(u, v\)について、共通の祖先であり、根頂点から最も遠い位置にあるLCAの頂点を求める。

ダブリングを使ったアルゴリズムでは、各頂点について\(2^K\)回(\(0 \le K \le \lceil \log N \rceil\))親に遡った時の頂点を計算しておく。 LCAを求める際は、\(u, v\)のそれぞれの祖先のうち、共通祖先となる頂点と共通祖先でない頂点の境目を2分探索で見つけて求める。

計算量

  • 前計算: \(O(N \log N)\)

  • クエリ処理: \(O(\log N)\)

実装

#include<algorithm>
#include<queue>
#include<vector>
using namespace std;

#define N 100003
#define LEV 21

class LCADoubling {
  int n, lev;
  int kprv[LEV][N], de[N];

  inline void construct_kprv() {
    for(int k=0; k<lev; ++k) {
      for(int i=0; i<n; ++i) {
        if(kprv[k][i] == -1) continue;
        kprv[k+1][i] = kprv[k][kprv[k][i]];
      }
    }
  }

public:
  LCADoubling(int n) : n(n) {
    int n0 = 1;
    lev = 0;
    while(n0 < n) n0 <<= 1, ++lev;
  }
  void construct(int *prv, int *depth) {
    for(int i=0; i<n; ++i) kprv[0][i] = prv[i], de[i] = depth[i];
    construct_kprv();
  }

  void construct_from_graph(vector<int> g[N], int s) {
    bool used[N];
    queue<int> que;
    for(int i=0; i<n; ++i) used[i] = false;

    used[s] = true;
    kprv[0][s] = -1; de[s] = 0;
    que.push(s);
    while(!que.empty()) {
      int v = que.front(); que.pop();
      for(int i=0; i<g[v].size(); ++i) {
        int w = g[v][i];
        if(used[w]) continue;
        used[w] = true;
        kprv[0][w] = v; de[w] = de[v] + 1;
        que.push(w);
      }
    }
    construct_kprv();
  }

  int query(int u, int v) {
    int dd = de[v] - de[u];
    if(dd < 0) {
      swap(u, v);
      dd = -dd;
    }

    // de[u] <= de[v]
    for(int k=0; k<=lev; ++k) {
      if(dd & 1) {
        v = kprv[k][v];
      }
      dd >>= 1;
    }

    // de[u] == de[v]
    if(u == v) return u;

    for(int k=lev-1; k>=0; --k) {
      int pu = kprv[k][u], pv = kprv[k][v];
      if(pu != pv) u = pu, v = pv;
    }
    return kprv[0][u];
  }
};

Verified

  • AOJ: "GRL_5_C: Tree - Lowest Common Ancestor": source (C++14, 0.18sec)

  • AtCoder: "AtCoder Beginner Contest 133 - F問題: Colorful Tree": source (C++14, 481ms)