CPSCO Session2-G:MSTX - 思考の墓場

クラスカル法あたりの考え方をちゃんとわかっているかを問われている気がしてよかった。

問題

考察・解法

　最小全域木だしクラスカル法っぽく考えたい。まず $a_i = 0$ のとき、つまり $c=1$ の辺から優先的に使うことを考えてみる。このとき、もし $c=0$ の辺を使うことがあるとしたら、そのような辺は $x$ がどのような値でも最小全域木に必ず用いられる辺であることが言える。このような辺の集合を $must$ とする。 $must$ に属する辺はあらかじめ繋いでおいたグラフから初めて、その他の辺の使い方が $x$ の値によってどう変わるかを観察しよう。
　 $x=a_i$ のとき、重みが $a_i$ 以下である $c=0$ の辺を最小全域木に用いるかをクラスカル法で判定する。そして、そのような辺がなくなった後のグラフの連結成分の数を $s_i$ とすると、 $x=a_i$ のときに最小全域木に使われる $c=1$ の辺の本数は $s_i-1$ 本であることがわかる。なぜなら、ここからクラスカル法によって $c=1$ の辺をチェックした後に繋がれる可能性のある辺は $must$ に属する辺だけで、これらはあらかじめ繋いでおくことにしたからである。
　 $a_i$ を昇順にsortしておけば、これを素直にシミュレーションすることができ、時間計算量 $O(M\log{M} + Q\log{Q})$ ですべてのクエリに解答できる。

実装

Submission #6249727 - CPSCO2019 Session2
クラスカル法を2回回すのがやや面倒？