根付き木のライブラリを書いてみたよ

概要

書いてみたとはいえど、思いついたのをぱっとやっただけなんで、もっといい方法で実装できるかも。 根付き木に対して、エッジに可換なモノイドを乗っけることができる。 この際、何かしらの二点間のノード $u$ , $v$ に対しての高速なクエリ処理ができる。 更新クエリとかも使えないんで、使う用途はあんまりないかも。でもダブリングとかそういう系がでたら使える。

使える関数。

• add_edge(from, to, weight) : from-to のエッジを追加する(無向)。重みを乗っける $O(1)$
• build(root) : root を根とした根付き木を形成する(add_edgeの処理が全部終わったあと) $O(N \log N)$
• lca(u, v) : $u$ , $v$ における最小共通祖先を見つける $O(\log N)$
• query(u, v) : $u$ , $v$ 間のパスのクエリを求める $O(\log N)$

lca の計算量について、最初 2 分探索しないといけないから $O(\log^2 N)$ じゃないかと思っていたんだけれども、 すでに計算済みのダブリングしたものがあるからそれを活用すれば $O(\log N)$ に落とせることがわかった。 もうこれで怖くない。この計算量の改良は、 tubo28氏のライブラリ を勝手ながら参考にさせていただきました。助かりました。

なんで作ったの

ここからはお気持ち。AtCoder の MST + 1 という問題を解いた。 この問題は最小全域木に辺を一つ入れてそっちに辺が入れ替わるかという問題に帰着するが、 この際、その入れる辺 $(u, v)$ 間の辺の中にひとつでも $w$ より大きい辺があれば、その辺を取り除いて $(u, v)$ を新たな辺にする ことで新しい最小全域木が完成する。

そこで問題になるのが、$(u, v)$ 間の辺の中の最大の重みはなにかということである。 ここで、その最大値を探すために、木のダブリングを使ってある 頂点 $u$ の (1 << b) 個前の祖先までの範囲の最大値を取るということをした。 そうすれば、祖先について $O(\log N)$ で辺の最大値を出してくれる。

しかしいま問いているのは、$(u, v)$ 間についてであるので、そこで、lca によって最小共通祖先を求めて、 $u$ から lca まで、 $v$ から lca までの辺の最大値をとり、それを組み合わせれば求まるというわけである。

これを自前で実装したら、ちゃんとACした。めちゃくちゃ嬉しい。ただ実装がおもすぎる。 案の定、想定解は違い、クエリを先読みして、クラスカルの最中にクエリを処理することでACできる。 でもこれが思いつかなかったりする場合とかは、この根付き木の実装を書かないといけないので、ならばライブラリ化すればいいということになった。

ソースコード

感想

やはり自分の解法で問題を通すのはとても楽しい。解法を自力で思いつくようにやると、こういうのを味わえると思う。