Japanese Student Championship 2019 Qualification E - Card Collector
https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_e
We should calculate not the maximum spanning forest but the maximum pseudo forest. K - 種類数 β uses similar property. We know we can swap edges in any tree, and we can also swap edges in any pseudo tree. Thus, the optimal movement is to take the maximum edge we can use, and repeat this operation until we cannot add edges anymore.
Let us prove it. First, we bring the solution doesn't contain the heaviest edge. Let us prove that we can create better solution by adding the heaviest edge. When we add the heaviest edge into the solution, we have two cycles. We can reduce it to a pseudo tree by removing certain edge. The weight of the removed edge is less than the weight of the heaviest edge, so this solution is not worse than the previous one. After adding edge, we have to add the next edge. The situation has been a little changed, but what we should do doesn't change.
The structure appears in this problem is called matroid. Especially, this matroid is known as bicircular matroid.
