ABC120 D - Decayed Bridges - ツバサの備忘録

解法

全ての橋が崩れた状態では、どの島からも別の島へ行くことができません。
よって、不便さは $_{N}C _{2}$ 、すなわち $N(N-1)/2$ となります。
ということで、ここから逆に橋を組み立てていき、不便さを後ろから求めていくことにします。
今現在の不便さが $C$ で、次に $(a,b)$ を繋ぐ橋をかけるとします。
既に $a$ から $b$ へ行くことができる場合、不便さが減ることはないので、 $a$ から $b$ へ行くことができない場合を考えていきます。
$a$ 自身を含む、 $a$ から行くことができる島の個数を $A$ 、同様に $b$ から行くことができる島の個数を $B$ とします。
このとき、 $(a,b)$ に橋をかけることで、 $A$ に含まれる任意の島から、 $B$ に含まれる任意の島へ、新しくいくことができるようになるため、
不便さは $AB$ だけ減ります。
ということで、 $C-AB$ が、このときの不便さとなります。
そして、 $a$ 自身を含み、 $a$ から行くことができる島の個数は、 $A+B$ へ増えます。
あとはこれを繰り返し計算していけばよいのですが、この $a$ 自身を含み、 $a$ から行くことができる島の個数を計算するのに、自分はUnion-Find木を利用しました。
それぞれのグループの根の部分に、根自身を含み、根からいくことができる島の個数を記録しておくことで、高速に計算することができるようになります。
あとは、順番にシミュレーションをしていくことで、この問題のクエリにこたえることができるようになります。