差分
このページの2つのバージョン間の差分を表示します。
両方とも前のリビジョン前のリビジョン次のリビジョン | 前のリビジョン次のリビジョン両方とも次のリビジョン | ||
programming_algorithm:graph_theory:lowest_common_ancestor [2020/02/06] – [ダブリング] ikatakos | programming_algorithm:graph_theory:lowest_common_ancestor [2020/02/07] – ikatakos | ||
---|---|---|---|
行 15: | 行 15: | ||
| | ||
- | 元は根付き木でなくても、適当な頂点を根としてLCAを求められるようにしておくと、様々な用途に使える。 | + | 元は根付き木でなくても、適当な頂点を根としてLCAを求められるようにしておくと、様々な用途に使える。(追加で前計算する情報が必要になる場合がある) |
* 任意の2点間距離 | * 任意の2点間距離 | ||
- | * 任意の2頂点を含む部分木の深さ、要素数、などの情報 | + | |
+ | | ||
行 26: | 行 27: | ||
* Euler Tour + Range Minimum Query | * Euler Tour + Range Minimum Query | ||
- | * セグメント木 | ||
- | * Sparce Table | ||
* ダブリング | * ダブリング | ||
* Schieber-Vishkin algorithm | * Schieber-Vishkin algorithm | ||
- | ==== EulerTour + RMQ ==== | + | ==== EulerTour + RmQ ==== |
===オイラーツアー=== | ===オイラーツアー=== | ||
行 45: | 行 44: | ||
5 | 5 | ||
- | この変換により、木の祖先・子孫関係をわかりやすい形(1次元配列)で持つことができるため、 | + | この変換により、木の祖先・子孫関係を1次元配列で持つことができるため、 |
- | 1次元配列で扱える様々なデータ構造を利用できる。BIT、セグメント木、など。 | + | 1次元配列で扱える様々なデータ構造を利用できる(BIT、セグメント木など) |
===オイラーツアーを用いたLCA=== | ===オイラーツアーを用いたLCA=== | ||
- | LCAを求めるには、オイラーツアーで通りかかった順番に頂点と深さを記録していく。 | + | LCAを求めるには、オイラーツアーで通りかかった順番に頂点番号と深さを記録していく。 |
また、その過程で各頂点が最初に現れた位置も記録していく。 | また、その過程で各頂点が最初に現れた位置も記録していく。 | ||
(実際には、最初に現れた位置でなく、最初~最後までのどこかの位置であればよいが、通常は最初に記録しておくのが一番やりやすい) | (実際には、最初に現れた位置でなく、最初~最後までのどこかの位置であればよいが、通常は最初に記録しておくのが一番やりやすい) | ||
行 69: | 行 68: | ||
こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。 | こうすると、頂点 $a$ と $b$ のLCAは、以下で求められる。 | ||
- | * それぞれが '' | + | * それぞれが '' |
- | * $a_i \lt b_i$ と仮定する | + | * $p_a \lt p_b$ と仮定する |
- | * '' | + | * '' |
* そいつがLCAである(このような頂点はただ1つ存在する) | * そいつがLCAである(このような頂点はただ1つ存在する) | ||
頂点(a, b) = (5, 4) のLCAを求める | 頂点(a, b) = (5, 4) のLCAを求める | ||
- | → ai = 3, bi = 6 | + | → pa = 3, pb = 6 |
eular_tour[3: | eular_tour[3: | ||
- | この中で最小は (1, 1) なので、深さ1の頂点1がLCA | + | この中で最小は (1, 1) なので、深さ1の頂点「1」がLCA |
もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、'' | もし、LCAの頂点番号は不要で、深さだけが求められればいい場合、'' | ||
行 87: | 行 86: | ||
* 平方分割 | * 平方分割 | ||
* セグメント木 | * セグメント木 | ||
- | * Sparce | + | * Sparse |
+ | 基本的に更新は不要なので、前処理 $O(N \log{N})$、クエリ $O(1)$ で処理できるSparse Tableが高速。 | ||
==== ダブリング ==== | ==== ダブリング ==== | ||
- | 各頂点から、1個先の親、2個先の親、4個先の親、8個先の親、...を記録していく。 | + | LCAを求める別の方法。 |
+ | |||
+ | 各頂点から、1個先の親、2個先の親、4個先の親、8個先の親、...を記録していく。(便宜的に根の親は根とする) | ||
- | * '' | + | * '' |
* 頂点 $v$ から $2^k$ 個先の親の頂点番号 $u$ | * 頂点 $v$ から $2^k$ 個先の親の頂点番号 $u$ | ||
* '' | * '' | ||
* 頂点 $v$ の深さ $d$ | * 頂点 $v$ の深さ $d$ | ||
- | $k$ が小さい方から順に全頂点を埋めていくと、$k$ を求める際には $k-1$ の結果を利用できる。 | + | $k$ が小さい方から順に全頂点を埋めていくと、$double[k]$ を求める際には $double[k-1]$ の結果を利用できる。 |
- | 最も深い頂点が1発で根を通り越すような $k$ の直前で止める。 | + | 最も深い頂点が1発で根にたどり着くような $k$ で止める。 |
== $a,b$ の深さを合わせる == | == $a,b$ の深さを合わせる == | ||
- | $b$ の方が深いとし、深さの差が38(2進数で 100110)だったとする。 | + | 作業用の変数として $a_t,b_t$ を用意し、$a_t←a$、$b_t←b$ |
- | 立っているbitだけ頂点を遡っていく。0-indexedで1,2,5桁目が' | + | $b_t$ の方が深いとし、深さの差が38($=2^1+2^2+2^5$)だったとする。 |
- | | + | |
- | | + | |
- | | + | |
- | $b←b_4$ と代入しておく。 | + | この時点で |
== 同階層ながら互いに異なる、最も浅い祖先を求める == | == 同階層ながら互いに異なる、最も浅い祖先を求める == | ||
- | $a,b$ の深さは揃った。そこから1発で根を通り越さない最大の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。 | + | $a_t,b_t$ の深さは揃った。そこから1発で根を通り越さない最大の $k$ から、$k$ を1ずつ減らしながら以下を繰り返し行う。 |
- | * '' | + | * '' |
- | * '' | + | * '' |
* 同じなら何もしない | * 同じなら何もしない | ||
* $k$ を1減らして繰り返す | * $k$ を1減らして繰り返す | ||
* '' | * '' | ||
- | $k=0$ までやったら、$a,b$ の1つ親がLCM。 | + | $k=0$ までやったら、$a_t,b_t$ の1つ親がLCM。 |
++++ 実装例(Python) | | ++++ 実装例(Python) | | ||
- | (注: 未verify) | + | * Verify: [[https:// |
<sxh python> | <sxh python> | ||
行 139: | 行 140: | ||
任意の2頂点のLCAおよび距離を取得できるようにする | 任意の2頂点のLCAおよび距離を取得できるようにする | ||
""" | """ | ||
- | depths: list | ||
- | distances: list | ||
- | ancestors: list | ||
def __init__(self, | def __init__(self, | ||
行 151: | 行 149: | ||
d = 1 | d = 1 | ||
while d < max_depth: | while d < max_depth: | ||
- | next_ancestors = [prev_ancestors[prev_ancestors[v]] for v in range(n)] | + | next_ancestors = [prev_ancestors[p] for p in prev_ancestors] |
self.ancestors.append(next_ancestors) | self.ancestors.append(next_ancestors) | ||
d <<= 1 | d <<= 1 | ||
行 158: | 行 156: | ||
def _init_dfs(self, | def _init_dfs(self, | ||
q = [(root, -1, 0, 0)] | q = [(root, -1, 0, 0)] | ||
- | direct_ancestors = [0] * n | + | direct_ancestors = [-1] * (n + 1) # 頂点数より1個長くし、存在しないことを-1で表す。末尾(-1)要素は常に-1 |
while q: | while q: | ||
v, p, dep, dist = q.pop() | v, p, dep, dist = q.pop() | ||
行 167: | 行 165: | ||
return direct_ancestors | return direct_ancestors | ||
- | def lca(self, u, v): | + | def get_lca(self, u, v): |
du, dv = self.depths[u], | du, dv = self.depths[u], | ||
if du > dv: | if du > dv: | ||
行 187: | 行 185: | ||
def get_distance(self, | def get_distance(self, | ||
- | lca = self.lca(u, v) | + | lca = self.get_lca(u, v) |
return self.distances[u] + self.distances[v] - 2 * self.distances[lca] | return self.distances[u] + self.distances[v] - 2 * self.distances[lca] | ||
行 200: | 行 198: | ||
</ | </ | ||
++++ | ++++ | ||
+ | |||
+ | ===== ついでに求められる情報 ===== | ||
+ | |||
+ | ==== 2点間辺数、2点間距離 ==== | ||
+ | |||
+ | 頂点 $a,b$ を結ぶパスは、$c=lca(a, | ||
+ | |||
+ | 根から各頂点への距離を記録しておけば、簡単な計算で2点間距離を求めることができる。 | ||
+ | |||
+ | $a,b$ の距離: $dist[a]+dist[b]-2dist[c]$ | ||
+ | |||
+ | 「$a$ から根まで遡上し、根から $b$ まで下る、という経路の内、根~$c$ の往復分が無駄である」と考えるとよい。 | ||
+ | |||
+ | root | ||
+ | / | ||
+ | c e | ||
+ | / \ ... | ||
+ | | ||
+ | /\ | ||
+ | | ||
+ | |||
+ | === 2点間を結ぶパス中の1辺の最大(最小)コスト === | ||
+ | |||
+ | こちらは、もう少し面倒になる。 | ||
+ | |||
+ | max(min)には逆演算がないので、距離と同様に根から各頂点を結ぶパスの最大コストを記録してもダメ(その辺が根~$c$ に位置する場合、結局求めたい値はわからない)。 | ||
+ | |||
+ | LCAをダブリングで求める手法と同じようにすればよい。(この場合、LCA自体を求めるアルゴリズムもダブリングの方がわかりやすい) | ||
+ | |||
+ | * $maxp[k][v]$ | ||
+ | * $v$ から根に向かって $2^k$ 頂点を遡上するパスの中での最大コスト | ||
+ | |||
+ | $a~c$ 間の最大コストは、$a$ と $c$ の深さの差が例えば $d=2^1+2^2+2^5$ であれば、以下を求めればよい。 | ||
+ | |||
+ | * $\max(maxp[1][v], | ||
+ | * ただし、$v_p=v$ から $p$ 個遡上した頂点 | ||
+ | |||
+ | LCAもダブリングで実装していれば、これはLCAを求める過程で同時に求められる。 | ||
+ | |||
+ | $b$ からも同じことをして、その大きい方が、求める答えとなる。 | ||
+ | |||
===== バリエーション ===== | ===== バリエーション ===== |