差分

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

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
次のリビジョン両方とも次のリビジョン
programming_algorithm:graph_theory:lowest_common_ancestor [2019/11/29] – [EulerTour + RMQ] ikatakosprogramming_algorithm:graph_theory:lowest_common_ancestor [2019/12/04] – [ダブリング] ikatakos
行 50: 行 50:
 ===オイラーツアーを用いたLCA=== ===オイラーツアーを用いたLCA===
  
-LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で以下の情報も記録していく。+LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で各頂点が最初に現れた位置も記録していく。
  
   * ''eular_tour[i] = (d, v)''   * ''eular_tour[i] = (d, v)''
     * $i$ 番目に通りかかる頂点の(深さ, 頂点番号)     * $i$ 番目に通りかかる頂点の(深さ, 頂点番号)
-  * ''depth[v] = d'' 
-    * 頂点 $v$ の深さ 
   * ''first_appear[v] = i''   * ''first_appear[v] = i''
     * 頂点 $v$ がeular_tour上で初めて現れるindex     * 頂点 $v$ がeular_tour上で初めて現れるindex
行 63: 行 61:
      1  2                v: 0, 1, 3, 5, 3, 1, 4, 1, 0, 2, 0]      1  2                v: 0, 1, 3, 5, 3, 1, 4, 1, 0, 2, 0]
     / \     / \
-   3 4     depth = [0, 1, 1, 2, 2, 3] +   3 4     first_appear = [0, 1, 9, 2, 6, 3] 
-   |        first_appear = [0, 1, 9, 2, 6, 3]+   |
    5    5
  
行 105: 行 103:
 == $a,b$ の深さを合わせる == == $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]   b3 = double[b2][2]
-  b4 = double[b3][1] → b4とaで深さが揃った以降 b = b4 とする+  b4 = double[b3][5] → これでb4とaで深さが揃った 
 + 
 +以降 $b$ は $b_4$ のことを指すとする
  
 == 同階層ながら互いに異なる、最も浅い祖先を求める == == 同階層ながら互いに異なる、最も浅い祖先を求める ==
programming_algorithm/graph_theory/lowest_common_ancestor.txt · 最終更新: 2020/05/10 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0