こんばんは、お久しぶりです。今期アニメで一番好きな女の子はフーカ・レヴェントンちゃんです。
さて、CODE FESTIVAL 2016もいよいよ今週末に迫り、メールの届かなさも相まって緊張感が高まってきています。
というわけで、今回はあの忌々しき「LCA」なるものを克服しようと思い、二日かけてなんとか達成できたので、記事を書くことにします。
今回のテーマである「オイラーツアーとRMQを用いたLCA計算」は、蟻本(↓)にて詳しく紹介されています。
私は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)までの距離)+1
=1+2+1=4
となります。
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