HackerRank 101 Hack May 2016: Tree Splitting
完全制覇・ツリー上でのクエリ処理技法 - (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 の入った瞬間、出る瞬間のみを記録する。
5 の部分木を切り離す。
分離後の木の euler tour は、列の切り貼りで作れる。列の切り貼りは平衡二分探索木の merge/split を使えばいい。
入るときと出るときだけ記録しているので、（euler tour 列の長さ / 2） が丁度木のサイズになる。euler tour のサイズは木の root にメモってあるはずなので、それを使えばいい。
Hackerrank 101 Hack May 2016: Tree Splitting
部分木に対する update, query, cut ならこの手法でいけるかな。
link-cut tree を習得する機運が高まったけど筋肉だけついてもね…。
