いろいろな解き方があり、面白い。この問題を要約すると、$x$ と $y$ の連結成分のサイズの和 ($x$ と $y$ が連結なときは $x$ 成分のみのサイズだけ見る) が $z$ 以上になるような スコアの最小値はどこかという問題である。
たとえば、一つのクエリについてあるスコアを超えればすべて $z$ 以上になるので、スコアで二分探索ができる。 しかし、あるスコアについて見る時、そこまでの頂点を連結させる処理が必要になるので一回の計算ごとに $O(M)$ くらいかかってしまう(アッカーマンの逆関数については省く)。 そうすると、 $O(QM \log M)$ 程度かかってしまう。
そこで様々な工夫をすることで計算を早く行いたい。
まず１つの方針として、ある時系列の連結成分の情報について高速に取り出せるようにするという方法がある。
自分が最初に実装した方法だと、ある時刻 $t$ に起こった連結を保存する木(頂点数 $2 \times N-1$ )を生成し、 時刻 $t$ 以下に連結された部分木の中で、頂点 $x$ を含むような極大の部分木を高速に探す方法である。 そしてその部分木の葉の個数(実際の頂点はすべて葉であるため)を取れるようにしておけば、 $x$ がある $t$ のときの連結された成分の個数を高速に取れるというわけである。
これを実装するためには、そのような木のエッジに時刻の経過を意味するコストを入れて、根付き木を生成すると良い。 このとき、ダブリング辺にまとめた辺のコストの和を入れるようにすれば、葉からある祖先までたどったときに どの程度の時間が経過したのかがわかるので、それが $t$ 以下ならば進み、そうでないなら進まないというようにすることで 時刻 $t$ 以下の頂点 $x$ を含むような極大の部分木が $O(\log N)$ で見つけられる。 これで、クエリに対して二分探索と極大の部分木を探す計算量がかかるので、 $O(Q \log M \log N)$ で計算できる。
ちょっと重い。少なくとも 674ms 程度はかかるようだ。
この Union-Find は時系列データに対して使えるようである。何ができるかと言うと時刻 $t$ における連結情報を 保存しているのでそのときに何が連結しているかと、その時の連結成分の大きさを返せるというものである。 まさにこの問題で必要とされていることである。
普通の永続 Union-Find はおそらく時系列に対して 1 方向ではなく、木のように分岐させても状態を保存できるのかな？ ちょっとあまり調べてないのでわからないが、まあこの問題には 1 方向で十分である。
普通の Union-Find と違って経路圧縮ができないので各クエリの計算量が $O(\alpha(N))$ ではなくなってしまうが、 Union by rank か Union by size のつなぎ方をやっておけば、 $O(\log N)$ ですむので十分速いだろう。
実装方法は、親に連結された時間 $T_u$ を保存するのと、あるノードのある時刻における連結成分の大きさを保存することで、 ある時刻 $t$ のルートを見つけたいときは $T_u \leq t$ であるまで遡ればいいということがわかる。 また、サイズを知りたいときはまず $u$ のルート $r$ を見つけてから $r$ の連結成分の大きさについてのリストについて 二分探索すればある時刻までの連結成分の大きさを見つけられるといった感じである。
よってこの方法でも、クエリについて $O(Q \log M \log N)$ で調べられる。 こっちは $2$ 倍のノードを生成する必要もなくダブリングもする必要もないので定数倍が軽く、 228ms 程度で通る。
並列二分探索という、すべてのクエリに対して二分探索を $1$ 回進めてしまうという方法が想定解である。 今回は、連結情報を取るためにクエリごとに逐一 Union-Find を $O(M)$ 回回す必要があったが、 この連結させている最中に $Q$ 個のクエリを処理してしまおうというアイデアである。
二分探索の ok と ng という値をクエリごと( $ok_j, ng_j$ みたいに) に持っておく。 そして現在調べたいスコアというのは $(ok_j + ng_j) / 2$ であるので、 それぞれの調べたいスコアの位置にクエリを入れておくことにする。
すると、グラフを連結させた適切なタイミングでクエリがでてくるので、その時の $x_j$ と $y_j$ のサイズについて 見るだけで済み、このときに すべての $j$ における二分探索を一つ進めることができる。
つまりこの連結させる処理を $O(\log M)$ 回程度行えば、すべての二分探索を終えることができる。 この計算量は $O((Q+M+N)\log M)$ 程度であり一番高速だと思う(アッカーマンの逆関数は除く)。 通してみたら 108 ms 程度だったのでこの３つの中では一番速いと思う。
データ構造も普通の Union-Find しか使わないので最もイージーな実装方法になっている。
Union-Find の実装やその他の非本質の部分は省く。
前に書いた 根付き木のライブラリを書いてみたよ の根付き木のライブラリに 多少関数を追加している(getAncestor, getAncestorDist)。 RootedTree のエッジを張ったら部分木について葉の数を計算しておき、 クエリ処理するという流れである。
こっちは割とこじんまりとしている。$t$ は昇順に入れる必要がある。
クエリの処理の方法の工夫。
並列二分探索などは、かなり使い勝手がいいと思った。ただ、クエリ内で二分探索する系って多いのかな？ だけれども、色々と知れるのはやはり嬉しい。1000 点問題で橙 Diff であるが、思いつきやすい問題ではあったと思う。 ただデータ構造を知らないで普通に実装しようとするとかなり難しいなと思う。 逆にデータ構造さえ知っていれば貼ればいいみたいな状態ではあったので結構知識ゲーなのかなとも思った。