差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン | 次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:graph_theory:lowest_common_ancestor [2019/11/28] – [EulerTour + RMQ] ikatakos | programming_algorithm:graph_theory:lowest_common_ancestor [2019/11/29] – [EulerTour + RMQ] ikatakos | ||
---|---|---|---|
行 33: | 行 33: | ||
==== EulerTour + RMQ ==== | ==== EulerTour + RMQ ==== | ||
- | オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で以下の情報も記録していく。 | + | ===オイラーツアー=== |
+ | |||
+ | オイラーツアーは、深さ優先探索で通りかかった順番に頂点を記述する方法。$N-1$ 辺を行き帰りで2回ずつとおるので、出発点と合わせて長さ $2N-1$ の配列になる。 | ||
+ | |||
+ | 0 | ||
+ | / \ | ||
+ | | ||
+ | / \ | ||
+ | 3 4 | ||
+ | | | ||
+ | 5 | ||
+ | |||
+ | この変換により、木の祖先・子孫関係をわかりやすい形(1次元配列)で持つことができるため、 | ||
+ | 1次元配列で扱える様々なデータ構造を利用できる。BIT、セグメント木、など。 | ||
+ | |||
+ | ===オイラーツアーを用いたLCA=== | ||
+ | |||
+ | LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で以下の情報も記録していく。 | ||
* '' | * '' | ||
- | * $i = 0 ~ 2(N-1)$ について、$i$ 番目に通りかかる頂点の(深さ, | + | * $i$ 番目に通りかかる頂点の(深さ, |
* '' | * '' | ||
* 頂点 $v$ の深さ | * 頂点 $v$ の深さ | ||
行 52: | 行 69: | ||
こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。 | こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。 | ||
- | * '' | + | * それぞれが |
* $a_i \lt b_i$ と仮定する | * $a_i \lt b_i$ と仮定する | ||
- | * '' | + | * '' |
- | * そいつがLCAである | + | * そいつがLCAである(このような頂点はただ1つ存在する) |
- | 頂点5と4 | + | 頂点(a, b) = (5, 4) のLCAを求める |
+ | | ||
eular_tour[3: | eular_tour[3: | ||
この中で最小は (1, 1) なので、深さ1の頂点1がLCA | この中で最小は (1, 1) なので、深さ1の頂点1がLCA | ||
行 63: | 行 81: | ||
もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、'' | もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、'' | ||
+ | ===区間最小値=== | ||
ここで、区間の最小値を求めるクエリRmQが発生する。以下のアルゴリズムなどで解ける。 | ここで、区間の最小値を求めるクエリRmQが発生する。以下のアルゴリズムなどで解ける。 |