差分

この文書の現在のバージョンと選択したバージョンの差分を表示します。

--- programming_algorithm:graph_theory:lowest_common_ancestor [2019/12/04]
ikatakos [ダブリング]
+++ programming_algorithm:graph_theory:lowest_common_ancestor [2020/05/10] (現在)
ikatakos [ダブリング]
@@ ライン 1: / ライン 1: @@
 ====== 最小共通祖先 ======
-Lowest Common Ancestor, LCA, 最近共通祖先などといわれる。「共通祖先」で検索すると、生物進化方面の用語が混じって出てくる。
+Lowest Common Ancestor, LCA, 最近共通祖先などといわれる。「共通祖先」で検索すると生物進化方面の用語が混じって出てくるので記事をやや探しづらい。
   * [[https://yukicoder.me/wiki/lowest_common_ancestor|Lowest Common Ancestor - yukicoder Wiki]]
@@ ライン 15: / ライン 15: @@
    ６          １と２のLCAは１
-元は根付き木でなくても、適当な頂点を根としてLCAを求められるようにしておくと、様々な用途に使える。
+元は根付き木でなくても、適当な頂点を根としてLCAを求められるようにしておくと、様々な用途に使える。（追加で前計算する情報が必要になる場合がある）
   * 任意の2点間距離
-  * 任意の2頂点を含む部分木の深さ、要素数、などの情報
+  * 任意の2点間を結ぶパス上の最小コスト辺、最大コスト辺
+  * 任意の2頂点を含む部分木の要素数
@@ ライン 26: / ライン 27: @@
   * Euler Tour + Range Minimum Query
-    * セグメント木
-    * Sparce Table
   * ダブリング
   * Schieber-Vishkin algorithm
-==== EulerTour + RMQ ====
+==== EulerTour + RmQ ====
 ===オイラーツアー===
@@ ライン 45: / ライン 44: @@
    ５
-この変換により、木の祖先・子孫関係をわかりやすい形（1次元配列）で持つことができるため、
+この変換により、木の祖先・子孫関係を1次元配列で持つことができるため、
-次元配列で扱える様々なデータ構造を利用できる。BIT、セグメント木、など。
+次元配列で扱える様々なデータ構造を利用できる（BIT、セグメント木など）
 ===オイラーツアーを用いたLCA===
-LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で各頂点が最初に現れた位置も記録していく。
+LCAを求めるには、オイラーツアーで通りかかった順番に頂点番号と深さを記録していく。
+また、その過程で各頂点が最初に現れた位置も記録していく。
+（実際には、最初に現れた位置でなく、最初～最後までのどこかの位置であればよいが、通常は最初に記録しておくのが一番やりやすい）
   * ''eular_tour[i] = (d, v)''
@@ ライン 67: / ライン 68: @@
 こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。
-  * それぞれが ''eular_tour'' 上ではじめて現れるindex $a_i,b_i$ を取得する
+  * それぞれが ''eular_tour'' 上ではじめて現れるindex $p_a,p_b$ を取得する
-    * $a_i \lt b_i$ と仮定する
+    * $p_a \lt p_b$ と仮定する
-  * ''euler_tour''上で、区間 $[a_i, b_i]$ 内から、depthが最小となる頂点を取得する
+  * ''euler_tour''上で、区間 $[p_a, p_b]$ 内から、depthが最小となる頂点を取得する
   * そいつがLCAである（このような頂点はただ1つ存在する）
   頂点(a, b) = (5, 4) のLCAを求める
-    → ai = 3, bi = 6
+    → pa = 3, pb = 6
   eular_tour[3:6] = [(3, 5), (2, 3), (1, 1), (2, 4)]
-  この中で最小は (1, 1) なので、深さ1の頂点１がLCA
+  この中で最小は (1, 1) なので、深さ1の頂点「1」がLCA
 もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、''eular_tour'' で管理するのは $d$ のみでよい。
@@ ライン 85: / ライン 86: @@
   * 平方分割
   * セグメント木
-  * Sparce Table
+  * Sparse Table
+基本的に更新は不要なので、前処理 $O(N \log{N})$、クエリ $O(1)$ で処理できるSparse Tableが高速。
 ==== ダブリング ====
-各頂点から、1個先の親、2個先の親、4個先の親、8個先の親、...を記録していく。
+ダブリングは、
-  * ''double[v][k] = u''
+  * 前計算で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$ が小さい方から順に全頂点を埋めていくと、$k$ を求める際には $k-1$ の結果を利用できる。
+$k$ が小さい方から順に全頂点を埋めていくと、$double[k][v]=double[k-1][double[k-1][v]]]$ と直前の結果を利用できる。
-最も深い頂点が1発で根にたどり着けるような $k$ で止める。
+最も深い頂点が1発で根にたどり着くような $k$ で止める。
 == $a,b$ の深さを合わせる ==
-$b$ の方が深いとし、深さの差が38（2進数で 100110）だったとする。
+作業用の変数として $a_t,b_t$ を用意し、$a_t←depth[a]$、$b_t←depth[b]$ とする。
-立っているbitだけ頂点を遡っていく。0-indexedで1,2,5桁目が'1'なので、
+$b_t$ の方が深いとし、深さの差が38（$=2^1+2^2+2^5$）だったとする。
-  b2 = double[b ][1]
+  bt = double[1][bt]
-  b3 = double[b2][2]
+  bt = double[2][bt]
-  b4 = double[b3][5] → これでb4とaで深さが揃った
+  bt = double[5][bt] → これでbtとatで深さが揃った
-以降 $b$ は $b_4$ のことを指すとする。
+この時点で $a_t=b_t$ であれば、LCAは $a$ である。以下、それ以外の場合を考える。
 == 同階層ながら互いに異なる、最も浅い祖先を求める ==
-$a,b$ から1発で根にたどり着けるような最小の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。
+$a_t,b_t$ の深さは揃った。そこから1発で根を通り越さない最大の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。
-  * ''double[a][k] != double[b][k]'' なら
+  * ''double[k][at] != double[k][bt]'' なら、$2^k$ 先の親に移動
-    * ''a ← double[a][k], b ← double[b][k]''
+    * ''at ← double[k][at], bt ← double[k][bt]''
   * 同じなら何もしない
-  * ''k ← k-1''
+  * $k$ を1減らして繰り返す
+    * ''k ← k-1''
+$k=0$ までやったら、$a_t,b_t$ の1つ親がLCM。
+++++ 実装例(Python) |
+  * Verify: [[https://atcoder.jp/contests/abc014/submissions/9925357|提出 #9925357 - AtCoder Beginner Contest 014]]
+<sxh 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
+</sxh>
+++++
+===== ついでに求められる情報 =====
+==== 2点間辺数、2点間距離 ====
+頂点 $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
+==== 2点間を結ぶパス中の1辺の最大（最小）コスト ====
+こちらは、もう少し面倒になる。
+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を求める過程で同時に求められる。
-$k=0$ までやったら、$a,b$ の1つ親がLCM。
+$b$ からも同じことをして、その大きい方が、求める答えとなる。