Toptree - Link & Cut編
引き続き, toptreeの解説をしていきます.
Link
link(v, w): 頂点vとwを辺vwで結ぶをします.
場合分けが多すぎるんじゃ
が, vの次数が0, 1, 2以上で処理が変わり, またwの次数が0, 1, 2以上で処理が変わります. (ちなみに論文はどちらも次数2以上のときのことしか書いてない, 全部書けや)
まず, expose(v)をした結果はこんな感じに次数で場合分けできます. exposeした後, 次数1のときに右側にvが来るようにします(左にあるときはreverseします)
expose(w)をしたときはこんな感じ. exposeした後, 次数1のときに左側にwが来るようにします.
vが右側, wが左側なのは, ... - vとw - ...をつなげて ... - v - w - ...としたいからです.
次に, w側のtoptreeから処理していきます.
ここでは, ... - v - w - ...のv - w - ...の部分を作ります.
このそれぞれの木の根をv-w-と表すことにして,
v側のtoptreeとつなげます. つなげ方は, vの次数によって場合分けです. つなげるとこんな感じ
... - v - w - ...になっていると思います.
Cut
cut(v, w): 頂点vとwを結んでいる辺vwを切ります
linkの逆操作をすればいいです.
soft_exposeを思い出してみましょう.
vwは辺なので, 図中の丸vwはCompress Nodeではなく, Edge Nodeのはずです.
また, degree(v) >= 2, degree(w) >= 2のパターンを見ると, N_w以下がlinkでのv - w - ...の部分を作るときと形が同じです.
まあなので逆操作をするとcutができます.
記事を分けたの失敗
LinkとCut重いなあと違う記事にしたけど, 図を作ったらそんなに重くなかった
次はクエリの捌き方を書きます(これは流石に分けないとまずい)
