101 Hack May 2016: Tree Splitting (link-cut tree 解)
https://www.hackerrank.com/contests/101hack37/challenges/tree-splitting
link-cut tree で解けるということは知っていたので、link-cut tree で解法を考えてみた。
euler tour を用いた解法はこちら。
解法
link-cut tree のノードに次の情報を追加する。
- solid-edge で繋がれた頂点の部分木のサイズ
- dashed-edge で繋がれた頂点の部分木のサイズ
dashed と solid が変わりそうなのは expose, link, cut の 3 つである。solid,dashed が入れ替わるタイミングで dashed-sub も一緒に更新する。
(1) expose
b が solid->dashed, c が dashed->solid。
(2) link
b が solid->dashed。
(3) cut
変化なし。
splay 操作では solid, dashed が入れ替わらないので、正しい部分木のサイズを計算できる。
expose, link, cut は平衡二分探索木の根のポインタの張り替えなので、dashed-sub の更新がただちに子に影響することはない。つまり正しい部分木のサイズを計算できる。
また、link, cut は根を含むパス上での操作なので、他のパスの部分木のサイズに影響しない。
データ構造の拡張を考えるの楽しい。これは木に限定した削除可能 union-find になってるのかな。一般グラフで削除可能 union-find を作るにはどうしたらいいんだろう。