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 を用いた解法はこちら。

pekempey.hatenablog.com

解法

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。

f:id:pekempey:20160531190532p:plain

(2) link
b が solid->dashed。

f:id:pekempey:20160531190537p:plain

(3) cut
変化なし。

f:id:pekempey:20160531190540p:plain

splay 操作では solid, dashed が入れ替わらないので、正しい部分木のサイズを計算できる。

expose, link, cut は平衡二分探索木の根のポインタの張り替えなので、dashed-sub の更新がただちに子に影響することはない。つまり正しい部分木のサイズを計算できる。

また、link, cut は根を含むパス上での操作なので、他のパスの部分木のサイズに影響しない。

データ構造の拡張を考えるの楽しい。これは木に限定した削除可能 union-find になってるのかな。一般グラフで削除可能 union-find を作るにはどうしたらいいんだろう。