HHKBプログラミングコンテスト2022 Winter (AtCoder Beginner Contest 282) D - Make Bipartite 2 (400)
最初に元のグラフについて考える
連結成分毎にDFSで色を塗っていき二部グラフになっているか考える
なっていなかったらどう辺を足してもそこは二部グラフでは無いので答えは0
二部グラフならその連結成分内で直接結ばれてない違う色同士の点同士は辺を足してもどれでも二部グラフ
このようなペアの個数は$ ある色の点の数 \times もう一方の色の点の数 - 既存の辺の数になる
既存の辺は全て違う色同士を結んでいないといけないため
また違う連結成分同士の点はどれを繋いでも二部グラフのままになるのでこの個数も答えに足す
これは連結成分毎に$ 連結成分内の点の個数 \times (全体の点の数 - 連結成分内の点の個数)を求めて和を半分にした数で求められる