読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

HackerRank 101 Hack May 2016: Tree Splitting

www.hackerrank.com

完全制覇・ツリー上でのクエリ処理技法 - (iwi) { 反省します - TopCoder部 に書いてある euler tour tree と同じものだと思うけどどうなんだろう。

(追記:2016/06/25)本物の euler tour tree は全然違うものでした。

問題

n 頂点の木が与えられる。頂点 v と連結している要素数を答え、v を削除するというクエリを m 回処理せよ。

  • オンラインクエリ

解法

辺の削除を実現すればいい。

euler tour と二分探索木を使うことで、v の部分木を切り離すという操作が O(log n) で可能になるのでこれを使う。

まず dfs して euler tour の列を構成。ただしこの euler tour では dfs の入った瞬間、出る瞬間のみを記録する。

f:id:pekempey:20160518064537p:plain

5 の部分木を切り離す。

f:id:pekempey:20160518064837p:plain

分離後の木の euler tour は、列の切り貼りで作れる。列の切り貼りは平衡二分探索木の merge/split を使えばいい。

f:id:pekempey:20160518065040p:plain

入るときと出るときだけ記録しているので、(euler tour 列の長さ / 2) が丁度木のサイズになる。euler tour のサイズは木の root にメモってあるはずなので、それを使えばいい。

Hackerrank 101 Hack May 2016: Tree Splitting

部分木に対する update, query, cut ならこの手法でいけるかな。 link-cut tree を習得する機運が高まったけど筋肉だけついてもね…。