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

シェアする

  • このエントリーをはてなブックマークに追加

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

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

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

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

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

LCAとは?

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

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

lowest_common_ancestor(図は 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(深さ優先探索)で探索した順に訪れたノード番号を配列に記録するものです。

sorted_binary_tree_preorder-svg

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

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

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする