最初のMSTに使われなかったいくつかの辺の重みが0になったとする。path optimality conditionを考えると、それらの辺を全域木に加えてできたサイクルから最大重みの辺を除く、を繰り返せば最適になるので、最初の全域木に使われている辺+重み0になった辺だけでMSTを求めても正しい結果が得られる。重みを元に戻した時も、「最初のMSTに使われなかった辺がいくつか0になった状態」であることには変わりないので同じである。したがって、重みが$0$になっている辺と最初の全域木に使われた辺だけを見て毎回Kruskalなどをするという方針は正しい。
ただ、更新クエリによって重み0の辺が増えていくと、質問クエリで走査する辺の数は結局${O}(Q+N)$になってしまうので厳しそうに見える。各時点での重み$0$の辺によるconnectivityをundo可能Union-Findに保持しておいて(offline dynamic connectivity)、毎回そこからKruskalをする方針だと辺の数は${O}(N)$のままなので、全体の計算量は${O}(Q (\log Q + N)\log N + M \log M)$にはなりそう。これでもぎりぎりに見えるが…… → 解説を見た。掛かる定数が小さいので${O}(Q + N)$でよいということらしい。
- 愚直Union-Find 1.46 sec.
- offline dynamic connectivity 1.01 sec.
undo付きにするとUnion-Findが遅くなるのでどうかと思ったけれど、一応速くはなるらしい。
