ABC014 D「閉路」 – RMQを用いたLCA

Pocket

こんばんは、お久しぶりです。今期アニメで一番好きな女の子はフーカ・レヴェントンちゃんです。

さて、CODE FESTIVAL 2016もいよいよ今週末に迫り、メールの届かなさも相まって緊張感が高まってきています。

というわけで、今回はあの忌々しき「LCA」なるものを克服しようと思い、二日かけてなんとか達成できたので、記事を書くことにします。

今回のテーマである「オイラーツアーとRMQを用いたLCA計算」は、蟻本（↓）にて詳しく紹介されています。

<br />

私はC#のコードを書いたので、C++での解説が欲しい場合は蟻本を買いましょう。

LCAとは？

LCAとは、Lowest Common Ancestorの略で、「最近共通祖先」とか言われます。最低共通祖先とは言われないんですね、なぜか。

これは根付き木に対する概念で、木の2つのノードが出会うためには、どこまで親へ辿って行けばいいのか、という問題の答えになります。

（図は https://commons.wikimedia.org/

wiki/File:Lowest_common_ancestor.svg by Qwertyus より引用）

右図において、矢印が向いているノードを親とすると、xとyの共通の祖先（親または親の親または……）は、薄い緑と濃い緑の3つのノードです。

その中で最もxとyに近い（すなわち低い・深い）共通祖先が濃い緑のノードで、これが最近共通祖先（LCA）です。

今回の「閉路」の問題では、右図の木が与えられたとき、xとyのノードを結んでできる閉路の長さは、

（xからLCA(x,y)までの距離）＋（yからLCA(x,y)までの距離）＋１

＝１＋２＋１＝４

となります。

LCAが高速に求められれば、閉路の長さも高速に求められます。

今回の問題では、O(NQ)では通らないので、LCAの計算にO(N)は掛けられません。O(logN)とかで求める必要があります。

LCAをO(logN)程度で計算する方法は「ダブリング」というものもあるようですが、そっちは苦手なので今回は「オイラーツアー」と「RMQ」を用いて実装します。

オイラーツアーとは

オイラーツアーとは、木の根ノードから出発してDFS（深さ優先探索）で探索した順に訪れたノード番号を配列に記録するものです。

右図の木に対してオイラーツアーを行うと、

F,B,A,B,D,C,D,E,D,B,F,G,I,H,I,G,F

となります（実際にはノード番号は文字ではなく数字で管理するので数列になります）。

この配列をvs[]とします。

これの何が良いかというと、「部分列が必ず部分木になる」という性質があるのです。

例えば、上の列から”D,C,D,E,D,B,F,G”を取り出すと、これに含まれるノードD,C,E,B,F,Gは元の木の部分木になっています。

ノードxとノードyを含む部分木を得るには、「最初にxを訪れたときのvs[]の場所」と「最初にyを訪れたときのvs[]の場所」の間の部分を見ればいいです。例えば、上の例でAとCなら、

“A,B,D,C”となります。こうすると、必ず、無駄なところには行かないような部分木が得られます。ここに”唯一”含まれる共通祖先がLCA、すなわち最近共通祖先になります。

さらに、オイラーツアーで訪れたノードを記録するときに、その時の深さも記録しておきます。

index	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
vs	F	B	A	B	D	C	D	E	D	B	F	G	I	H	I	G	F
depth	0	1	2	1	2	3	2	3	2	1	0	1	2	3	2	1	0

さらに、各ノードについて、「最初にそのノードを訪れたときにvs[]にメモしたインデックス（添字）」を記録しておきます。これをid[]とすると、

ノード	A	B	C	D	E	F	G	H	I
id	2	1	5	4	7	0	11	13	12

となります。すると、LCA(x,y)は「xとyを含む（無駄のない）部分木に含まれるノードの中で、最も浅いもの」となります。部分木にはxとyの共通祖先が必ず1つだけ含まれ、それは最も浅いからです。

つまり

LCA(x,y)＝vs[id[x] ≦ i ≦ id[y] を満たす i の中で、depth[i]を最小にする i]

として得ることができます。

上の例で、LCA(A,C)を求めるときは、id[A]=2, id[C]=5なので、depth[2]からdepth[5]までを見ると

2 1 2 3

となるので、最小値は1であり、そのときのインデックスは3になっています。

したがって、LCA(A,C)=vs[3]=B が得られます。

そして、この「区間最小を求める」という計算で、セグメント木を用いたRMQを利用します。

ただし、今回は区間内の最小値ではなく「区間内の最小値の場所（インデックス）」を得る必要があるので注意です。

これは、セグメント木のノードを pair(最小値, インデックス) という構造にすれば実現可能になりますが、ここでは詳しくは書きません。

参考：指定区間の最大値／最小値のインデックスを求めるクエリにたくさん答えたい part1（http://hama-du-competitive.hatenablog.com/entry/2016/10/12/003723）

以上を実現した提出コードがこちら↓

http://abc014.contest.atcoder.jp/submissions/989567

Pocket