hackercupai/hackercup huggingface dataset:
We can observe that the weight of the minimum spanning tree is equal to the sum of all edge weights in the graph (*Quantity 1*), minus the weight of one removed edge per circle (*Quantity 2*), minus the weight of one additional removed edge somewhere in the graph (*Quantity 3*).

For *Quantity 3*, the additional removed edge may either be any inter-circle edge, or *potentially* a second edge within some circle. There are two categories of circles:

- If \(X_i = Y_i\), no two of its edges can be validly removed (without disconnecting the graph).
- Otherwise, if \(X_i \ne Y_i\), the circle can be considered to have two "halves" (the paths connecting its \(X_i\)th and \(Y_i\)th nodes clockwise and counterclockwise), such that up to one edge may be validly removed from *each* half (without disconnecting the graph).

For each circle \(i\), we'll define three values of interest:

- Let \(R_i\) be the maximum weight of any edge within the circle. This will help with computing *Quantity 2*.
- Let \(P_i\) be the maximum possible combined weight of any validly-removable pair of edges within the circle (if any). If \(X_i = Y_i\) (meaning that only one of its edges may be removed), we'll let \(P_i = R_i\) instead.
- Let \(D_i = P_i - R_i\). The represents the additional amount by which the minimum spanning tree's weight can be decreased if two edges are removed from the circle, and will help with computing *Quantity 3*.

Then, for each circle \(i\), we'll maintain:

- An ordered multiset of all edge weights within it (used to compute \(R_i\)).
- If \(X_i \ne Y_i\), two additional ordered multisets containing all edge weights in each of its halves (used to compute \(D_i\)).

On top of that, we'll globally maintain:

- The sum of all edge weights in the graph (*Quantity 1*).
- The sum of all circles' \(R_i\) values (equivalent to *Quantity 2*).
- An ordered multiset of all circles' \(D_i\) values, and another containing all inter-circle edge weights (combined to compute *Quantity 3*).

Each event (and initial edge) requires us to update just a constant number of the above values and multisets, each taking logarithmic time (provided that the multisets are implemented using BBSTs). Therefore, this solution has a time complexity of \(O((NM + E) (log(N) + log(M)))\).