最近、Online Dynamic Connectivityとか言われているデータ構造を実装しようと奮闘しています。
これを実装するのにEuler Tour Treeというのが必要なのですが、結構面白かったので備忘録です。

ちなみに、以下のスライドを参考にしているというか、なぞっているだけです。
https://web.stanford.edu/class/cs166/lectures/15/Slides15.pdf

Online Dynamic Connectivityはこちらのスライドが詳しいです。
https://web.stanford.edu/class/cs166/lectures/16/Slides16.pdf

Euler Tour Treeとは

辺のlink/cutや、根の変更(reroot)、2頂点が同じ木に属しているか(are-connected)を $O(\log N)$ 時間で行うことのできる、動的木と呼ばれるデータ構造の一種です。

森の状態の管理にEuler Tourを利用します。

Euler Tourを利用した各クエリの捌き方の概要

どのようにEuler Tourを利用するのか、link/cut/reroot/are-connectedのやり方を見ていきます。

link

例として、以下のような森を考えます。

このとき

$0$ を根とする木のEuler Tourは $(0, 1), (1, 0)$
$2$ を根とする木のEuler Tourは $(2, 3), (3, 2), (2, 4), (4, 2)$

となります。
この2つの木を、 $0, 2$ 間でlinkするにはどうすればいいでしょうか？

結論から言えば、2つのEuler Tourを $(0, 2)$ を挟んで連結して、最後に $(2, 0)$ を加えると、2つの木を $0, 2$ 間で連結したEuler Tourを作ることができます。
実際、

$(0, 1), (1, 0), \color{red}{(0, 2),} (2, 3), (3, 2), (2, 4), (4, 2)\color{red}{, (2, 0)}$

は、新しい木のEuler Tourになっていることがわかります。

このように、木の根同士を連結する場合には、2つの木のEuler Tourを適当な頂点対を挟んで連結して片割れを最後にくっつければ、linkができます。
木の根同士ではないときは、後述のrerootで連結したい頂点を根に変更すればよいです。

cut

先ほどの例のlink後の状態から、さらに $3$ の下に頂点が増えた木のEuler Tourを考えます。

$(0, 1), (1, 0), (0, 2), (2, 3), (3, 5), (5, 3), (3, 2), (2, 4), (4, 2), (2, 0)$

これを $2, 3$ 間でcutすることを考えます。
まずは $(2, 3), (3, 2)$ を削除してみます。

$(0, 1), (1, 0), (0, 2), \color{red}{(2, 3),} (3, 5), (5, 3), \color{red}{(3, 2),} (2, 4), (4, 2), (2, 0)$
↓
$(0, 1), (1, 0), (0, 2), \color{white}{(2, 3),} (3, 5), (5, 3), \color{white}{(3, 2),} (2, 4), (4, 2), (2, 0)$

$(3, 5), (5, 3)$ は、cut後の $3$ を頂点とする木のEuler Tourになっていそうです。

前後の列について考えると、 $2, 3$ 間をcutすることを $3$ の部分木のEuler Tourをなかったことにすると考えれば、真ん中の列を無視してくっつければそのまま $0$ を根とする木のEuler Tourになりそうです。
実際、

$(0, 1), (1, 0), (0, 2), (2, 4), (4, 2), (2, 0)$

は、 $2, 3$ 間をcutした後の $0$ を根とする木のEuler Tourです。

このように、cutする辺を列から削除し、真ん中を無視して前後の列をくっつけることで、cutは達成できます。

reroot

linkの例の木について、根を $0$ から $2$ に変更することを考えます。

    0               2
   / \             /|\
  1   2    ->     0 3 4  
     / \         /
    3   4       1

左の木のEuler Tourは以下の通りです。

$(0, 1), (1, 0), (0, 2), (2, 3), (3, 2), (2, 4), (4, 2), (2, 0)$

唐突ですが、この列をローテートして、末尾の $(2, 0)$ が先頭に来るようにしてみます。

$(0, 1), (1, 0), (0, 2), (2, 3), (3, 2), (2, 4), (4, 2), \color{red}{(2, 0)}$
↓
$\color{red}{(2, 0),} (0, 1), (1, 0), (0, 2), (2, 3), (3, 2), (2, 4), (4, 2)$

ビックリですが、ローテート後の列は上記の絵の右の木のEuler Tourになっています。
このように、rerootは根にしたい頂点が始点になっている辺が先頭に来るように列のローテートを行うだけで達成できます。

例えば、 $(2, 3)$ が先頭に来るようにローテートしても、rerootは達成できます。

$(0, 1), (1, 0), (0, 2), \color{red}{(2, 3),} (3, 2), (2, 4), (4, 2), (2, 0)$
↓
$\color{red}{(2, 3),} (3, 2), (2, 4), (4, 2), (2, 0), (0, 1), (1, 0), (0, 2)$

このEuler Tourは、以下のような木を表し、やはり $2$ が根になります。

$(2, 4)$ でローテートしてもよいですが、例は省略です。

are-connected

これは方法自体は簡単で、チェックしたい2頂点が含まれる辺が同じEuler Tourの列に含まれるかどうかを確認すればよいです。

データの持ち方

今まで見てきたように、列を任意の点で効率的に分割・連結できることが要求されます。

このようなデータ構造としてはまず双方向連結リストと辞書の組み合わせが考えられます。
辺が列のどこにあるかはハッシュテーブルのようなデータ構造の辞書であれば $O(1)$ で求められ、列の分割・連結も連結リストなら $O(1)$ なので、非常に効率が良いです。

しかし、are-connectedはどうやってやればいいでしょうか？
たぶんいい方法はなくて、列を $O(N)$ で走査して確認するしかないです。なので、双方向連結リスト+辞書はパスです。

次に、平衡二分木を検討します。
分割・連結は $O(\log N)$ に悪化しますが、are-connectedは、辞書でポインタを持ち、根まで遡ってみるなどの方法で $O(\log N)$ でできますから現実的です。

また、頂点固有の情報の持ち方についても考える必要があります。
Euler Tourは辺の情報しか持たないので、頂点の情報を引き出すのはツライです。
どこかの辺に押し付けることは可能ですが、どの辺が頂点の情報を持っているのかを効率的に求めることは難しいです。
そこで、自己ループをEuler Tourに混ぜ込み、それを頂点をみなすことで解決します。

実装

Rustで実装していきます。
平衡二分木に何を使うかですが、私はSplay木しか書けないので、Splay木でいきます。

すべての左部分木の頂点はEuler Tourにおいて自身より前に位置する辺、右部分木は自身より後ろに位置する辺、というルールにしておきます。

実用的には何か演算を乗せて使うことが多いのでしょうが、とりあえずは上記のクエリが捌けるものを作っていきましょう。

基本的にソラで書いていくので、ちょっとずつ仕様が変わっていくかもしれません。
完全な実装例だけが必要なら、後述のremove-packetまで実装したやつを見るのがよいと思います。

Splay木の実装

実装例：Rust Playground

循環データ構造が必要です。たぶんRust的にお行儀よく書くにはRc/Weakなどの参照カウンタを用いるのがよいですが、どうせ内部データ構造で外に露出しないので、ポインタでいきます。

親・子へのポインタには生ポインタを持ってもよいですが、Option<NonNull>を使うのが便利です。
NULLポインタ最適化でサイズも生ポインタと変わらなくなるはずなので、効率を落とさず、NULLの扱いを便利にできます。

NonNull<Node>のままだと扱いにくいので、NodeRefというラッパを作っていい感じに使えるようにします。
Box::leakで'staticな参照を得られます。解放するときはBox::from_rawで所有権を取り戻して捨てればよいです。

split/mergeが必要になるかもしれませんが、とりあえずsplayさえ使えればいいので、今のところはここまででOKです。

Euler Tour Treeの初期化

実装例：Rust Playground

各頂点を表す自己ループへのポインタへのアクセスは軽いほうがよいので、配列で持ちます。
それ以外の辺へのポインタは辞書で持ちます。

ちょっとSplay木のNodeの定義を変えて、辺の始点・終点を持つようにしました。
indexはこれを代わりに使えるので、削除です。

are-connectedの実装

実装例：Rust Playground

対象の2つの頂点をsplayして順に根に持ってきます。
同じ木に属するのであれば、先にsplayしたほうは根ではなくなるはずです。

コーナーケースとして、与えられた頂点が同じ、というのがあるので気をつけましょう。当然2回splayしても根のままです。

rerootの実装

実装例：Rust Playground

根にしたい頂点が始点である辺の直前ならどこで切ってもいいのですが、せっかく自己ループには効率的にアクセスできるので、自己ループの前で切る、というルールにします。

自己ループをsplayして平衡二分木の根にし、左部分木を切って最も右の子の右部分木としてくっつけます。

split/mergeを実装してもよいですが、まあそこまでしなくていいかと思ったので実装しません。

linkの実装

実装例：Rust Playground

are-connected/rerootを実装したので、これを利用してlinkが実装できます。

まず、同じ頂点かどうかや、すでに辺があるかどうかは簡単に判定できるので弾きます。
また、木じゃなくなるとマズいので、are-connectedでlinkしたい頂点が同じ木に属していないことも確認します。

こういった不正なクエリをどうするかですが、とりあえず無視することにしておきます。
Resultを返すようにしておくと、デバッグなどで役に立つこともあるかもしれません。

次はlinkしたい頂点をrerootでそれぞれの木の根に変更します。

その後は先述の通り、適切な辺を生成して平衡二分木のマージを行います。
新しく生成した辺は辞書に収めておきます。

cutの実装

実装例：Rust Playground

自己ループや、辺がない頂点間のcutはできないので、冒頭で弾きます。

辺がある場合は辞書から対になる辺と併せて引き出します。
これを削除して列の前後をくっつけるわけですが、引き出した2つの辺のどっちがEuler Tourで前に位置するかをわかっていないといけません。

私は、とりあえず片方splayして左右部分木を切り離した後、もう片方をsplayし、部分木の根の変化を調べることで前後を調べることにしました。
あるいは、Nodeに部分木サイズを持たせるようにし、それぞれが前から何番目かを都度計算して調べるとかでもできると思います。

最後は不要になった辺を削除しますが、確保した領域を解放しないともれなくメモリリーク発生です。
valgrind --tool=memcheckなどで試験しておくといいと思います。

ここまで実装するとテストらしいテストができるようになるので、テストコードも最下部に追加しました。
雑なテストですが、Splay木の実装がバグっていたのを修正すると、だいたいのケースで上手くいきそうかなというのは確認できました。

Euler Tour Treeの機能拡張

ここまでで最低限の機能はできましたが、参考にしたスライドでは、

ある頂点が属する木の頂点数を調べるsize
ある頂点にパケットを付加するadd-packet
ある頂点から到達可能な範囲にある頂点に付加されたパケットをどれか1つ取り除くremove-packet

という拡張が紹介されています。

これらはEuler Tour Treeを利用したOnline Dynamic Connectivityの実装に役立つので、ついでに実装していきます。

sizeの実装

実装例：Rust Playground

Nodeを拡張してsizeというメンバを持たせ、平衡二分木の部分木の値の集約を実装します。
自己ループのNode以外は集計してはいけないので、Node::newとNode::updateの実装に注意です。

平衡二分木の部分木の値集約が実装出来たら、あとは引数として与えられた頂点を表す自己ループをsplayして、sizeの値を返せばよいです。

テストにsizeのクエリを追加しました。まあ多分ですが、上手く動いているでしょう…

add-packetの実装

実装例：Rust Playground

ここでは、各頂点が持つパケットの個数情報はNodeで持たないことにします。
個数情報を各Nodeで持つのはメモリ効率が悪すぎるので、必要なら別途それを管理するデータ構造を用意したほうが良いと思います。

これを踏まえて、Nodeには、

自身がパケットを持っているかを示すhas_packetフラグ
自身を根とする部分木の頂点のうち、自身を除くいずれかがパケットを持っているかを示すhas_packet_subtreeフラグ

を持たせます。ただ、それぞれをboolで持つのはメモリの無駄なので、u8でビットマップにして持ちます。
実装では、0ビット目がhas_packetフラグ、1ビット目がhas_packet_subtreeフラグです。

これらのデータの管理も、平衡二分木の部分木の値集約でできるので、Node::updateの実装を修正します。

EulerTourTree側のメインの処理としては、対象の頂点を平衡二分木の根にしてフラグをセットし、Node::updateを呼ぶ、といったシンプルなものになります。

remove-packetの実装

実装例：Rust Playground

スライドの通り、どの頂点のパケットを除くかは指定できないことにしておきます。
この実装を利用してfind-packet(パケットを持つ到達可能頂点のどれかを返す)を実装し、狙い撃ちでパケットを除去するバージョンを作ることもできます。

実装は単純で、has_packetフラグを持つ頂点に辿り着くまで、has_packetかhas_packet_subtreeが立っている子を辿ります。

has_packetフラグを持つ頂点が見つかったら、splayで平衡二分木の根にして、Node::remove_packetを呼び出してフラグをクリアし、Node::updateで整合性を取ります。

add-packetの分もクエリを追加してテストを回してみると、上手くいっていそうです。

ここまでで、スライドに載っているクエリはすべて捌けるようになったと思います。

おわりに

結局このデータ構造って、オイラーツアーを平衡二分木に乗せました！っていうただそれだけなわけですが、それだけでこんな色々なことができるんだなあって思いました。

同じ動的木でも、Link-Cut Treeはもっとものすごいことやっていたのでさすがにソラで実装できる気はしないですが、Euler Tour Treeはその気になればその場で書けちゃいそうです。

あとは値と演算を乗せるとか、作用を伝播させるとかができるとよいですが、パフォーマンスの面でも実用できるレベルにするにはもう少し工夫が必要そうです。

ちょっと疑問な部分としては、部分木全体の値集約は簡単にできますけど、パスの値集約ってEuler Tour Treeでも捌けるんですかね？
それは未だに分かっていません。

競プロ備忘録

競プロerの備忘録

Euler Tour Treeを書く

Euler Tour Treeとは

Euler Tourを利用した各クエリの捌き方の概要

link

cut

reroot

are-connected

データの持ち方

実装

Splay木の実装

Euler Tour Treeの初期化

are-connectedの実装

rerootの実装

linkの実装

cutの実装

Euler Tour Treeの機能拡張

sizeの実装

add-packetの実装

remove-packetの実装

おわりに