問題

グラフ ${G=(V,E)}$ 中の辺に番号 ${1,\dots,|E|}$ がつけられている。クエリ ${(x_i,y_i,z_i)}$ ${(i=1,\dots,Q)}$ が与えられるので、「辺 ${1,\dots,p}$ のみを残した部分グラフ ${G_p=(V,E_p)}$ 中で頂点集合 ${x_i}$ または ${y_i}$ から到達可能な頂点が ${z_i}$ 個以上になる」ような ${p}$ の最小値を各 ${i}$ について求めよ。

解法

愚直にやるなら各クエリに対してN要素のUnion-Findを作り、辺1から順に両端の頂点をuniteしていく。到達可能な頂点数（ ${x_i}$ と ${y_i}$ が非連結なら ${size(x_i)+size(y_i)}$ ）が ${z_i}$ 以上になる時の辺番号が答えとなる。 ${O(QM\alpha(N))}$ でTLE。

愚直手法ではuniteして ${size(x_i)}$ を調べる操作をクエリあたり ${M}$ 回もループしているので、平方分割によりこれを減らせば間に合う。あらかじめ ${0,\sqrt{M},2\sqrt{M},\dots}$ までuniteした ${\sqrt{M}}$ 個のUnion-Findを構築しておけば、各クエリは「 ${k\sqrt{M}\leq ans_i}$ < ${(k+1)\sqrt{M}}$ となる ${k}$ を二分探索で見つける→ ${k\sqrt{M}}$ のUnion-Findからスタートして、辺を1つずつuniteする(最大 ${\sqrt{M}}$ 回)→解 ${ans_i}$ を見つけたら使ったUnion-Findを元に戻す(revert)」操作で処理できる。以下の解答コードではUnion-Findの経路圧縮をしていないので、計算量 ${O(M\log N+N\sqrt{M}+Q\sqrt{M}\log N)}$ (1.4sでAC)．第1項は辺1...Mをuniteする操作、第2項は ${\sqrt{M}}$ 個のUnion-Findを保存する操作、第3項はクエリの処理。