最小共通祖先

Lowest Common Ancestor, LCA, 最近共通祖先などといわれる。「共通祖先」で検索すると生物進化方面の用語が混じって出てくるので記事をやや探しづらい。

• Lowest Common Ancestor - yukicoder Wiki

根付き木において、頂点 $a$ と頂点 $b$ を根に向かって辿っていった時、最初に合流する頂点のことを指す。

     １
    /  \
   ２  ３    ５と６のLCAは２
  / \
 ４ ５       ３と４のLCAは１
 ｜
 ６          １と２のLCAは１

元は根付き木でなくても、適当な頂点を根としてLCAを求められるようにしておくと、様々な用途に使える。（追加で前計算する情報が必要になる場合がある）

• 任意の2点間距離
• 任意の2点間を結ぶパス上の最小コスト辺、最大コスト辺
• 任意の2頂点を含む部分木の要素数

求め方は複数のアルゴリズム・実装が知られている。

• Euler Tour + Range Minimum Query
• ダブリング
• Schieber-Vishkin algorithm

オイラーツアーは、深さ優先探索で通りかかった順番に頂点を記述する方法。$N-1$ 辺を行き帰りで2回ずつとおるので、出発点と合わせて長さ $2N-1$ の配列になる。

     ０
    /  \   
   １  ２    0, 1, 3, 5, 3, 1, 4, 1, 0, 2, 0
  / \
 ３ ４
 ｜
 ５

この変換により、木の祖先・子孫関係を1次元配列で持つことができるため、 1次元配列で扱える様々なデータ構造を利用できる（BIT、セグメント木など）

LCAを求めるには、オイラーツアーで通りかかった順番に頂点番号と深さを記録していく。 また、その過程で各頂点が最初に現れた位置も記録していく。 （実際には、最初に現れた位置でなく、最初～最後までのどこかの位置であればよいが、通常は最初に記録しておくのが一番やりやすい）

• eular_tour[i] = (d, v)
  • $i$ 番目に通りかかる頂点の（深さ, 頂点番号）
• first_appear[v] = i
  • 頂点 $v$ がeular_tour上で初めて現れるindex

     ０
    /  \   eular_tour = [d: 0, 1, 2, 3, 2, 1, 2, 1, 0, 1, 0
   １  ２                v: 0, 1, 3, 5, 3, 1, 4, 1, 0, 2, 0]
  / \
 ３ ４     first_appear = [0, 1, 9, 2, 6, 3]
 ｜
 ５

こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。

• それぞれが eular_tour 上ではじめて現れるindex $p_a,p_b$ を取得する
  • $p_a \lt p_b$ と仮定する
• euler_tour上で、区間 $[p_a, p_b]$ 内から、depthが最小となる頂点を取得する
• そいつがLCAである（このような頂点はただ1つ存在する）

頂点(a, b) = (5, 4) のLCAを求める
  → pa = 3, pb = 6
eular_tour[3:6] = [(3, 5), (2, 3), (1, 1), (2, 4)]
この中で最小は (1, 1) なので、深さ1の頂点「1」がLCA

もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、eular_tour で管理するのは $d$ のみでよい。

ここで、区間の最小値を求めるクエリRmQが発生する。以下のアルゴリズムなどで解ける。

• 平方分割
• セグメント木
• Sparse Table

基本的に更新は不要なので、前処理 $O(N \log{N})$、クエリ $O(1)$ で処理できるSparse Tableが高速。

ダブリングは、

• 前計算で1個先、2個先、4個先、8個先、… の結果を求めていく。たとえば8個先は「4個先の4個先」のように直前の結果を利用できる
• 前計算結果を利用すると、たとえば21個先は「1個先の4個先の16個先」とたかだか $\log{N}$ 回の遷移で求められる

というアルゴリズム。これをLCAを求めるのに適用する。

各頂点から、1個先の親、2個先の親、4個先の親、8個先の親、…を記録していく。（便宜的に根の親は根とする）

• double[k][v] = u
  • 頂点 $v$ から $2^k$ 個先の親の頂点番号 $u$
• depth[v] = d
  • 頂点 $v$ の深さ $d$

$k$ が小さい方から順に全頂点を埋めていくと、$double[k][v]=double[k-1][double[k-1][v]]]$ と直前の結果を利用できる。 最も深い頂点が1発で根にたどり着くような $k$ で止める。

作業用の変数として $a_t,b_t$ を用意し、$a_t←depth[a]$、$b_t←depth[b]$ とする。

$b_t$ の方が深いとし、深さの差が38（$=2^1+2^2+2^5$）だったとする。

bt = double[1][bt]
bt = double[2][bt]
bt = double[5][bt] → これでbtとatで深さが揃った

この時点で $a_t=b_t$ であれば、LCAは $a$ である。以下、それ以外の場合を考える。

$a_t,b_t$ の深さは揃った。そこから1発で根を通り越さない最大の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。

• double[k][at] != double[k][bt] なら、$2^k$ 先の親に移動
  • at ← double[k][at], bt ← double[k][bt]
• 同じなら何もしない
• $k$ を1減らして繰り返す
  • k ← k-1

$k=0$ までやったら、$a_t,b_t$ の1つ親がLCM。

実装例(Python)

class LcaDoubling:
    """
    links[v] = { (u, w), (u, w), ... }  (u:隣接頂点, w:辺の重み)
    というグラフ情報から、ダブリングによるLCAを構築。
    任意の2頂点のLCAおよび距離を取得できるようにする
    """

    def __init__(self, n, links, root=0):
        self.depths = [-1] * n
        self.distances = [-1] * n
        prev_ancestors = self._init_dfs(n, links, root)
        self.ancestors = [prev_ancestors]
        max_depth = max(self.depths)
        d = 1
        while d < max_depth:
            next_ancestors = [prev_ancestors[p] for p in prev_ancestors]
            self.ancestors.append(next_ancestors)
            d <<= 1
            prev_ancestors = next_ancestors

    def _init_dfs(self, n, links, root):
        q = [(root, -1, 0, 0)]
        direct_ancestors = [-1] * (n + 1)  # 頂点数より1個長くし、存在しないことを-1で表す。末尾(-1)要素は常に-1
        while q:
            v, p, dep, dist = q.pop()
            direct_ancestors[v] = p
            self.depths[v] = dep
            self.distances[v] = dist
            q.extend((u, v, dep + 1, dist + w) for u, w in links[v] if u != p)
        return direct_ancestors

    def get_lca(self, u, v):
        du, dv = self.depths[u], self.depths[v]
        if du > dv:
            u, v = v, u
            du, dv = dv, du
        tu = u
        tv = self.upstream(v, dv - du)
        if u == tv:
            return u
        for k in range(du.bit_length() - 1, -1, -1):
            mu = self.ancestors[k][tu]
            mv = self.ancestors[k][tv]
            if mu != mv:
                tu = mu
                tv = mv
        lca = self.ancestors[0][tu]
        assert lca == self.ancestors[0][tv]
        return lca

    def get_distance(self, u, v):
        lca = self.get_lca(u, v)
        return self.distances[u] + self.distances[v] - 2 * self.distances[lca]

    def upstream(self, v, k):
        i = 0
        while k:
            if k & 1:
                v = self.ancestors[i][v]
            k >>= 1
            i += 1
        return v

頂点 $a,b$ を結ぶパスは、$c=lca(a,b)$ として、$a$ から $c$ までは木を遡上し、$c$ から $b$ まで下ることとなる。

根から各頂点への距離 $dist[v]$ を記録しておけば、簡単な計算で2点間距離を求めることができる。

$a,b$ の距離: $dist[a]+dist[b]-2dist[c]$

「$a$ から根まで遡上し、根から $b$ まで下る、という経路の内、根～$c$ の往復分が無駄である」と考えるとよい。

     root
     /  \
    c    e
   / \   ...
 ...  b
  /\
 a  d

こちらは、もう少し面倒になる。

max(min)には逆演算がないので、距離と同様に根から各頂点を結ぶパスの最大コストを記録してもダメ（その辺が根～$c$ に位置する場合、結局求めたい値はわからない）。

LCAをダブリングで求める手法と同じようにすればよい。この場合、LCA自体を求めるアルゴリズムもダブリングの方がわかりやすい。

• $maxp[k][v]$
  • $v$ から根に向かって $2^k$ 頂点を遡上するパスの中での最大コスト

$a～c$ 間の最大コストは、$a$ と $c$ の深さの差が例えば $d=2^1+2^2+2^5$ であれば、以下を求めればよい。

• $\max(maxp[1][v], maxp[2][v_2], maxp[5][v_6])$
• ただし、$v_p=v$ から $p$ 個遡上した頂点

LCAもダブリングで実装していれば、これはLCAを求める過程で同時に求められる。

$b$ からも同じことをして、その大きい方が、求める答えとなる。

木の構造が定まっているので、bit演算で計算できる。手順はダブリングと似ている。

根を1とし、頂点 $x$ の子を頂点 $2x,2x+1$ とする。こうすると、頂点番号のbit長が、その頂点の深さと一致する。

1. $a,b$ のbit長が異なる場合、長い方（深い方）を、短い方にあわせて右bitshiftする
   1. $b$ の方が長く、$a$ に合わせた結果を $b'$ とする
2. 上位bitから、$a$ と $b'$ がどこまで一致するか見ていく。下から数えて $i$ 桁目で食い違ったとする
3. $a$ を $i$ 桁 右bitshiftしたものが答え

    １            0001
   /  \          /    \
  ２  ３      0010     0011
  /\  /\      / \       / \
 ４５６７  0100 0101 0110 0111

３と４のLCA
1. ４(0100)を３(0011)にあわせて2桁にする → (0010)
2. (0010)と(0011)を先頭から一致するまで見ていく。下1桁で食い違う
3. (0010)を1桁 右bitshiftした (0001) がLCA