コンテストページ: HHKB Programming Contest 2022 Winter(AtCoder Beginner Contest 282) - AtCoder
コンテスト後にAC: A〜C
コンテスト後にD,Eは自力で解けず。Fは自力AC

D - Make Bipartite 2

コンテスト中はよくわからない勘違いでACできませんでした。

まず、連結成分に2部グラフでないものが含まれていた場合、辺追加後のグラフも2部グラフにならないので0です(これが抜けていました)。以下、全ての連結成分が2部グラフであるとします。

まず、連結成分内同士を繋ぐ場合の辺の本数を求めます。
連結成分の1つ $C$ について、頂点を2つの独立集合 $U=\{u_1,\cdots ,u_k\}$ と $V=\{v_1,\cdots ,v_m\}$ に分けます。これは頂点を2色彩色した場合に同色となる頂点集合と同じです。

$U$ または $V$ 内で辺を繋ぐと2部グラフでなくなります。 $U$ と $V$ の頂点同士はどのように繋いでも2部グラフのままです。

$U$ の任意の頂点 $u$ について、 $V$ の全ての頂点と辺を繋ぐことが可能なので、合計 $m$ 本の辺を繋ぐことができるわけですが、既に辺が存在する場合はその分を引かなければなりません。

つまり、 $u$ は $m-N(u)$ 本の辺を繋ぐことができます。但し、 $N(u)$ は $u$ から出ている辺の本数とします。
従って、連結成分内で繋げる辺の本数は $i=1,\cdots ,k$ について、 $u_i$ で繋げる辺の本数の総和を求めればよいです。

次に、連結成分間です。
任意の連結成分 $C_i,C_j$ 間では、全ての頂点間の辺を繋ぐことができます。もし、頂点を2色彩色した場合の同色同士を辺で繋いだとしても、一方の連結成分の色を全て反転させればよいです。

よって、連結成分 $C_1,\cdots C_{i-1}$ の頂点数の合計が $S$ であり、 $C_i$ の頂点数が $|C_i|$ だとすれば、 $S\times |C_i|$ 本の辺を繋ぐことができます。
以上から、連結成分間について、連結成分の頂点数の和を順次計算しながら、辺の本数を求めていくことができます。