競プロチャレンジ供養会場: AtCoder Beginner Contest 214 D - Sum of Maximum Weights

コンテストでの時間切れや解けなかった過去問を振り返って供養していく

問題

Difficulty: 1341 (記事作成時点)

供養

解法

• ある連結成分で最も重みの大きな辺を $uv$、重みを $w$ として、連結成分を $uv$ で分割したときに $u$ が所属する側の点集合を $U$、$v$ が所属する側の点集合を $V$ とすると、任意の $u^{'} \in U, v^{'} \in V$ の組合せについて $f(u^{'}, v^{'}) = w$ となる
• よって、$\sum_{u^{'} \in U}\sum_{v^{'} \in V}f(u^{'}, v^{'}) = |U| \times |V| \times w$
• 上記を再帰的に適用することで重みの合計を得ることができる
• 適用を逆から見ていくと、最も重みの小さな辺を使って連結成分を結合していき、その時の結合する連結成分の大きさと重みの積の和が答えとなることがわかる

実装

計算量は $O(N \log N)$

公式解説

躓いた点

• 小さい順に見る発想が出なかった