この記事は、「木 Advent Calendar 2023」の12日目です。
昨日の記事はまぐふらいさんの「みなとみらい駅にあるやつ」でした。
明日の記事はまぐふらいさんの「木上の巡回セールスマン問題」です。
Link Cut Treeを知っていますか？
Link Cut Treeとは、根付き森を動的に扱うデータ構造です。
具体的には、以下のような操作が $O(\log N)$ でできます。
-
link(v, u): $v$ の親を $u$ にする（ただしvはある根付き木の根であること） -
cut(v): $v$ を根とする部分木を元の木から切り離す -
root(v): $v$ が含まれる木の根を求める-
root(u) == root(v): $u, v$ が同じ木に属するか判定する
-
-
evert(v): $v$ が含まれる木の辺の向きを変更して、 $v$ を根にする - パスに対する頂点・辺の値のクエリに答える
- sum
- max
- 更新
図で表すと、以下のような感じです。
link(v, u)
cut(v)
evert(v)
UnionFind のような使い方
Link Cut Tree は根付き木を扱うものですが、操作をうまく組み合わせることで無向木を扱うことができます。
たとえば、 UnionFind における union(u, v) クエリは以下のように実現できます:
-
evert(v)でvを根にする -
link(v, u)でvをuの下につなげる
Link Cut Treeの構造
参考程度にサラっと。
Link Cut Treeでは、Heavy-Light Decompositionがするように、木をいくつかのパスに分割します。
そして、それぞれのパスをひとつの頂点として縮約します。
ひとつひとつのパスは、Splay Treeという平衡二分木を使って表現されます。
木をこのようなパスが集まった「パスの木」として扱うことで、さまざまなクエリを高速に処理します。
なお、木に対して操作をすると、縮約されるパスは変化します。
Link Cut Treeライブラリ（敬称略）
- Luzhiled's Library (ei13333, C++)
- Nyaan's Library (Nyaan, C++)
- rust-data-structures (niuez, Rust)
- yaketake08's 実装メモ (yaketake08, Python)
Link Cut Tree で解ける問題
※Link Cut Tree でなくてもよい問題もあり