CODE THANKS FESTIVAL 2017 H. Union Sets

この記事は 解説 Advent Calendar 2017 の10日目の記事です。
昨日は unko08658932 さんで「Code Thanks Festival 2017 F Limited Xor Subset 解説 (ありがとう2017F問題の想定解じゃないのを書きます)」でした。

問題

H: Union Sets - CODE THANKS FESTIVAL 2017 | AtCoder

解法

ほぼ解説の解法1とほぼいっしょなので、その解法を思いついた流れを整理しておく。

Union-Findである頂点aとある頂点bをuniteするとき、aの根をa'、bの根をb'と置くと、以下の二通りが考えられる

1. a'をb'に繋ぐ
2. b'をa'に繋ぐ

図にすると、以下のようになる

各操作でa'とb'の間に枝を張って木を作っておき、さらに繋げた側がいつ繋げたかを覚えておく。
(つまり、a'をb'に繋いだ場合、a'を何回目の操作で繋げたかを配列などに記憶しておく)

ここで、あるx, yについてのクエリを考える。
まず、Union-Find で頂点 x と y が同じ集合にない場合は -1 を返す。
それ以外の場合、まず先程作った木の上で LCA*1 を行うと、下の図のようにオレンジの頂点を求めることができる*2。
知りたいのは、下の図の緑の頂点が何回目の操作でオレンジの頂点と繋がったかである。

ここで、木の頂点vの深さをdepth[v]とする*3。
緑の頂点は、x から (depth[オレンジの頂点] - depth[x] - 1) 回親を辿った頂点(これを頂点 u とする)か、もしくは y から (depth[オレンジの頂点] - depth[y] - 1) 回親を辿った頂点(これを頂点 v とする)のいずれかである。
ただ、u, v のどちらが緑の頂点になるかが問題である。ここで、u, v のうち、緑の頂点ではない方の頂点を赤の頂点とする(下図参照)。

赤の頂点がオレンジの頂点と繋がる操作は、緑の頂点がオレンジの頂点と繋がる操作よりも必ず先に行われているという性質を考えると、頂点 u, v の両方求めておいて、それらがオレンジの頂点と何回目の操作で繋がったかについて求めて、その大きい方を答えればよい。
これはUnion-Findで木を作る途中で記憶してあるので、容易に答えられる。(ただし、u, v のいずれかがオレンジの頂点に一致する場合は、そのための処理が必要なので注意)

計算量

O(Mα(N) + (N + Q) log(N))

コード

感想

Union-Find + LCAという解法自体は割とすぐに求まったけど、LCAのライブラリがバグっており、散々だった。
ライブラリをちゃんと整備しておくことは大事。
おそらく人生最後のこどふぇす*4でパーカーを逃したため、非常に辛かった。

最後に

明日は ferin_tech15 さんで「何か書く」です。
一体何が書かれるのか楽しみですね。

*1:第二版 p.293 あたりに載っている。蟻本を読もう！

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

*2:全ての操作を終えた後にできるのは森であるが、適当な根 r を設定し、ある頂点の属する木の根が自分自身である場合に頂点 r と繋ぐと森を一つの根付き木にすることができるので、その上で LCA の前処理をダブリングで行っておく

*3:LCAをダブリングで求めた場合、これは既に求まっている

*4:社会人Dとかに行けば出られるが、そこまでAtCoderが存在しているのかとか、こどふぇす自体がなくなってないかとかが考えられる