競技プログラミング総合スレ 64

競技プログラミング総 ..

809:デフォルトの名無しさん
22/12/18 01:02:37.00 Un2uABCHM.net
>>808
vector<pair<long long, long long>> v;
に各連結成分の頂点数 {黒, 白} が入ってると思ってくれ
long long ans=0, sum=0;
for (auto [a,b] : v) {
ans += a*b // 同じ連結成分で違う色の2頂点の組の数
ans += (a+b)*sum; // 違う連結成分なら同色の2頂点も可
sum += a+b; // 見終わったやつは足す
}
あとは既に張られてる辺 M 本引けばいい

次ページ

続きを表示

1を表示