101 Hack May 2016: Tree Splitting (euler-tour tree 解)
https://www.hackerrank.com/contests/101hack37/challenges/tree-splitting
図は手書きです。曲線は面倒です。そのうち綺麗な図に直すかもしれません。
Euler-tour tree
Euler-tour tree は以下の操作が行える動的木。
- link(u,v) := u,v を辺で繋ぐ。
- cut(u,v) := u,v を繋ぐ辺を削除する。
操作を拡張すれば、
- is-connected(u,v) := u,v が同じ連結成分に属するか判定する。
- size(u) := u が属する連結成分のサイズを計算する。
などの操作も可能。連結成分に強いのかな。ただし木限定。
次のような木があったとする。
この木をぐるっと巡回する。巡回するときに使った辺番号のリストで木を表現する。この表現のメリットは、どこをスタート地点にしても回転シフトすれば同じ列になることである。つまりどこを根にするかという問題が生じない。
次の 2 つの木を link したい。
euler-tour の輪っかを繋ぎたい頂点の場所で切り、更に大きな輪を作る。これが link(u,v)。
cut(u,v) は u,v 辺を削除するだけ。
基本的に列の merge/split なので平衡二分探索木を使って管理する。原理が分かれば実装は難しくない。
euler-tour を辺番号で表現するか頂点番号で管理するかには選択の余地がある。
101 Hack May 2016: Tree Splitting (euler-tour tree ...
link/cut で merge/split をかなり呼び出しているので重い。速くしたい。
更新履歴
2016/09/06
- splitをボトムアップ実装にしました。わずかながら速くなったみたいです。
- 辺の管理に map を使っていましたが辺 ID で管理するようにしました。map を使わなくなった分それなりに高速化できたようです。ただし辺を先読みできる必要があります。
