差分
このページの2つのバージョン間の差分を表示します。
| 両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
| programming_algorithm:graph_theory:lowest_common_ancestor [2019/11/29] – [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:// | * [[https:// | ||
| 行 50: | 行 50: | ||
| ===オイラーツアーを用いたLCA=== | ===オイラーツアーを用いたLCA=== | ||
| - | LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で各頂点が最初に現れた位置も記録していく。 | + | LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。 |
| + | また、その過程で各頂点が最初に現れた位置も記録していく。 | ||
| + | （実際には、最初に現れた位置でなく、最初～最後までのどこかの位置であればよいが、通常は最初に記録しておくのが一番やりやすい） | ||
| * '' | * '' | ||
| 行 103: | 行 105: | ||
| == $a,b$ の深さを合わせる == | == $a,b$ の深さを合わせる == | ||
| - | $b$ の方が深いとし、深さの差が2進数で 100110 だったとする | + | $b$ の方が深いとし、深さの差が38（2進数で 100110）だったとする。 |
| - | 先頭のbitから頂点を遡っていく | + | 立っているbitだけ頂点を遡っていく。0-indexedで1, |
| - | b2 = double[b ][5] | + | b2 = double[b ][1] |
| b3 = double[b2][2] | b3 = double[b2][2] | ||
| - | b4 = double[b3][1] → b4とaで深さが揃った。以降 | + | b4 = double[b3][5] → これでb4とaで深さが揃った |
| + | |||
| + | $b←b_4$ | ||
| == 同階層ながら互いに異なる、最も浅い祖先を求める == | == 同階層ながら互いに異なる、最も浅い祖先を求める == | ||
| - | $a,b$ から1発で根にたどり着けるような最小の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。 | + | $a,b$ の深さは揃った。そこから1発で根を通り越さない最大の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。 |
| - | * '' | + | * '' |
| * '' | * '' | ||
| * 同じなら何もしない | * 同じなら何もしない | ||
| - | * '' | + | |
| + | | ||
| $k=0$ までやったら、$a, | $k=0$ までやったら、$a, | ||
