差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:graph_theory:lowest_common_ancestor [2019/11/29] – [EulerTour + RMQ] ikatakos | programming_algorithm:graph_theory:lowest_common_ancestor [2019/12/04] – [ダブリング] ikatakos | ||
---|---|---|---|
行 50: | 行 50: | ||
===オイラーツアーを用いたLCA=== | ===オイラーツアーを用いたLCA=== | ||
- | LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で以下の情報も記録していく。 | + | LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で各頂点が最初に現れた位置も記録していく。 |
* '' | * '' | ||
* $i$ 番目に通りかかる頂点の(深さ, | * $i$ 番目に通りかかる頂点の(深さ, | ||
- | * '' | ||
- | * 頂点 $v$ の深さ | ||
* '' | * '' | ||
* 頂点 $v$ がeular_tour上で初めて現れるindex | * 頂点 $v$ がeular_tour上で初めて現れるindex | ||
行 63: | 行 61: | ||
| | ||
/ \ | / \ | ||
- | 3 4 depth = [0, 1, 1, 2, 2, 3] | + | 3 4 first_appear |
- | | + | | |
5 | 5 | ||
行 105: | 行 103: | ||
== $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で深さが揃った。以降 b = b4 とする | + | b4 = double[b3][5] → これでb4とaで深さが揃った |
+ | |||
+ | 以降 | ||
== 同階層ながら互いに異なる、最も浅い祖先を求める == | == 同階層ながら互いに異なる、最も浅い祖先を求める == |