Toptree - Link & Cut編

Last updated Aug 5, 2019

• Algorithm

Toptree 導入編 - niuez’s diary

引き続き, toptreeの解説をしていきます.

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(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重いなあと違う記事にしたけど, 図を作ったらそんなに重くなかった

次はクエリの捌き方を書きます(これは流石に分けないとまずい)