Top Tree
Operations
操作に関わる木の頂点数の合計を$ n個とする
$ \mathtt{new\_vertex}(x)
値$ xを載せた頂点を作る
時間計算量 $ \Theta(1)
$ \mathtt{expose}(v)
$ a - v - bとなっているclusterをTop Treeの根にする
$ vの $ \mathtt{handle}がTop Treeの根になる
時間計算量 $ \Omicron(\log n) \ \mathrm{amortized}
$ \mathtt{link}(v, w, c)
$ vと$ wを値が$ cであるclusterで結ぶ
時間計算量 $ \Omicron(\log n)\ \mathrm{amortized}
$ \mathtt{cut}(v, w)
辺$ v - wを切る
時間計算量 $ \Omicron(\log n) \ \mathrm{amortized}
$ \mathtt{path}(v, w)
パス $ v - wを表すclusterを返す
時間計算量 $ \Omicron(\log n) \ \mathrm{amortized}
$ \mathtt{select}(v, f)
頂点$ vが含まれる木を関数$ fによって二分探索する
木の重心などを求めることができる
時間計算量 $ \Omicron(\log n) \ \mathrm{amortized}
Summary
例
Top Treeにするとこのような形
https://gyazo.com/dba1be05faf7521aca8b46b9820c6368
元の木
https://gyazo.com/cf409b3c8d34bd79fdc2805e01f01731
References
Notes
各頂点の次数を1以上にしたりすると, 実装が楽
$ \mathtt{expose, splay}をする前にtoptreeのrootまでの経路をたどって遅延伝搬をすることで, パスや部分木に関する更新クエリも処理することができる.
Implementations
Problems