差分
このページの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$ の配列になる。 | ||
| + | |||
| + | ０ | ||
| + | / \ | ||
| + | | ||
| + | / \ | ||
| + | ３ ４ | ||
| + | ｜ | ||
| + | ５ | ||
| + | |||
| + | この変換により、木の祖先・子孫関係をわかりやすい形（1次元配列）で持つことができるため、 | ||
| + | 1次元配列で扱える様々なデータ構造を利用できる。BIT、セグメント木、など。 | ||
| + | |||
| + | ===オイラーツアーを用いたLCA=== | ||
| + | |||
| + | LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。また、その過程で各頂点が最初に現れた位置も記録していく。 | ||
| * '' | * '' | ||
| - | * $i = 0 ～ 2(N-1)$ について、$i$ 番目に通りかかる頂点の（深さ, | + | * $i$ 番目に通りかかる頂点の（深さ, |
| - | * '' | + | |
| - | * 頂点 $v$ の深さ | + | |
| * '' | * '' | ||
| * 頂点 $v$ がeular_tour上で初めて現れるindex | * 頂点 $v$ がeular_tour上で初めて現れるindex | ||
| 行 46: | 行 61: | ||
| | | ||
| / \ | / \ | ||
| - | ３ ４ depth = [0, 1, 1, 2, 2, 3] | + | ３ ４ first_appear |
| - | | + | ｜ |
| ５ | ５ | ||
| こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。 | こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。 | ||
| - | * '' | + | * それぞれが |
| * $a_i \lt b_i$ と仮定する | * $a_i \lt b_i$ と仮定する | ||
| - | * '' | + | * '' |
| - | * そいつがLCAである | + | * そいつがLCAである（このような頂点はただ1つ存在する） |
| - | 頂点５と４ | + | 頂点(a, b) = (5, 4) のLCAを求める |
| + | | ||
| eular_tour[3: | eular_tour[3: | ||
| この中で最小は (1, 1) なので、深さ1の頂点１がLCA | この中で最小は (1, 1) なので、深さ1の頂点１がLCA | ||
| 行 63: | 行 79: | ||
| もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、'' | もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、'' | ||
| + | ===区間最小値=== | ||
| ここで、区間の最小値を求めるクエリRmQが発生する。以下のアルゴリズムなどで解ける。 | ここで、区間の最小値を求めるクエリRmQが発生する。以下のアルゴリズムなどで解ける。 | ||
