差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:graph_theory:lowest_common_ancestor [2019/11/28] – [EulerTour + RMQ] ikatakos
+++ programming_algorithm:graph_theory:lowest_common_ancestor [2019/12/26] – ikatakos
@@ 行 1: / 行 1: @@
 ====== 最小共通祖先 ======
-Lowest Common Ancestor, LCA, 最近共通祖先などといわれる。「共通祖先」で検索すると、生物進化方面の用語が混じって出てくる。
+Lowest Common Ancestor, LCA, 最近共通祖先などといわれる。「共通祖先」で検索すると生物進化方面の用語が混じって出てくるので記事をやや探しづらい。
   * [[https://yukicoder.me/wiki/lowest_common_ancestor|Lowest Common Ancestor - yukicoder Wiki]]
@@ 行 33: / 行 33: @@
 ==== EulerTour + RMQ ====
-オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で以下の情報も記録していく。
+===オイラーツアー===
+オイラーツアーは、深さ優先探索で通りかかった順番に頂点を記述する方法。$N-1$ 辺を行き帰りで2回ずつとおるので、出発点と合わせて長さ $2N-1$ の配列になる。
+       ０
+      /  \
+     １  ２    0, 1, 3, 5, 3, 1, 4, 1, 0, 2, 0
+    / \
+   ３ ４
+   ｜
+   ５
+この変換により、木の祖先・子孫関係をわかりやすい形（1次元配列）で持つことができるため、
+次元配列で扱える様々なデータ構造を利用できる。BIT、セグメント木、など。
+===オイラーツアーを用いたLCA===
+LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。
+また、その過程で各頂点が最初に現れた位置も記録していく。
+（実際には、最初に現れた位置でなく、最初～最後までのどこかの位置であればよいが、通常は最初に記録しておくのが一番やりやすい）
   * ''eular_tour[i] = (d, v)''
-    * $i = 0 ～ 2(N-1)$ について、$i$ 番目に通りかかる頂点の（深さ, 頂点番号）
+    * $i$ 番目に通りかかる頂点の（深さ, 頂点番号）
-  * ''depth[v] = d''
-    * 頂点 $v$ の深さ
   * ''first_appear[v] = i''
     * 頂点 $v$ がeular_tour上で初めて現れるindex
@@ 行 46: / 行 63: @@
      １  ２                v: 0, 1, 3, 5, 3, 1, 4, 1, 0, 2, 0]
     / \
-   ３ ４     depth = [0, 1, 1, 2, 2, 3]
+   ３ ４     first_appear = [0, 1, 9, 2, 6, 3]
-   ｜        first_appear = [0, 1, 9, 2, 6, 3]
+   ｜
    ５
 こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。
-  * ''ai = first_appear[a], bi = first_appear[b]''を取得する（それぞれの初登場index）
+  * それぞれが ''eular_tour'' 上ではじめて現れるindex $a_i,b_i$ を取得する
     * $a_i \lt b_i$ と仮定する
-  * ''euler_tour''上で、区間 $[a_i, b_i]$ 内に、depthが最小となる頂点がただ1つ存在する
+  * ''euler_tour''上で、区間 $[a_i, b_i]$ 内から、depthが最小となる頂点を取得する
-  * そいつがLCAである
+  * そいつがLCAである（このような頂点はただ1つ存在する）
-  頂点５と４ → ai = 3, bi = 6
+  頂点(a, b) = (5, 4) のLCAを求める
+    → ai = 3, bi = 6
   eular_tour[3:6] = [(3, 5), (2, 3), (1, 1), (2, 4)]
   この中で最小は (1, 1) なので、深さ1の頂点１がLCA
@@ 行 63: / 行 81: @@
 もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、''eular_tour'' で管理するのは $d$ のみでよい。
+===区間最小値===
 ここで、区間の最小値を求めるクエリRmQが発生する。以下のアルゴリズムなどで解ける。
@@ 行 86: / 行 105: @@
 == $a,b$ の深さを合わせる ==
-$b$ の方が深いとし、深さの差が2進数で 100110 だったとする (5,2,1桁目が'1')
+$b$ の方が深いとし、深さの差が38（2進数で 100110）だったとする。
-先頭のbitから頂点を遡っていく
+立っているbitだけ頂点を遡っていく。0-indexedで1,2,5桁目が'1'なので、
-  b2 = double[b ][5]
+  b2 = double[b ][1]
   b3 = double[b2][2]
-  b4 = double[b3][1] → b4とaで深さが揃った。以降 b = b4 とする
+  b4 = double[b3][5] → これでb4とaで深さが揃った
+$b←b_4$ と代入しておく。
 == 同階層ながら互いに異なる、最も浅い祖先を求める ==
-$a,b$ から1発で根にたどり着けるような最小の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。
+$a,b$ の深さは揃った。そこから1発で根を通り越さない最大の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。
-  * ''double[a][k] != double[b][k]'' なら
+  * ''double[a][k] != double[b][k]'' なら、$2^k$ 先の親に移動
     * ''a ← double[a][k], b ← double[b][k]''
   * 同じなら何もしない
-  * ''k ← k-1''
+  * $k$ を1減らして繰り返す
+    * ''k ← k-1''
 $k=0$ までやったら、$a,b$ の1つ親がLCM。