解法
全ての橋が崩れた状態では、どの島からも別の島へ行くことができません。
よって、不便さは、すなわち
となります。
ということで、ここから逆に橋を組み立てていき、不便さを後ろから求めていくことにします。
今現在の不便さがで、次に
を繋ぐ橋をかけるとします。
既にから
へ行くことができる場合、不便さが減ることはないので、
から
へ行くことができない場合を考えていきます。
自身を含む、
から行くことができる島の個数を
、同様に
から行くことができる島の個数を
とします。
このとき、に橋をかけることで、
に含まれる任意の島から、
に含まれる任意の島へ、新しくいくことができるようになるため、
不便さはだけ減ります。
ということで、が、このときの不便さとなります。
そして、自身を含み、
から行くことができる島の個数は、
へ増えます。
あとはこれを繰り返し計算していけばよいのですが、この自身を含み、
から行くことができる島の個数を計算するのに、自分はUnion-Find木を利用しました。
それぞれのグループの根の部分に、根自身を含み、根からいくことができる島の個数を記録しておくことで、高速に計算することができるようになります。
あとは、順番にシミュレーションをしていくことで、この問題のクエリにこたえることができるようになります。
感想
考察自体は結構スムーズに行けたのですが、実装に時間をかけました。ので、自分の中ではもう少しはやく解くことができた、と思っています。ですが、安定して400点問題をはやときできるようになってきている気がするので、うれしいです！
