Help for MST problem

Revision en1, by drunk_philosopher, 2019-05-26 09:59:20

Hello, I am trying to understand the editorial of the following problem

Link to Editorial

I understand the editorial completely except for the reduced formula to calculate the expected value.

It's Cmst — (sum of maximum cost edge across all paths)/T where T is n(n+1)/2.

I don't understand how the editorialist arrived at this. Can anybody provide an intuition behind this? Thanks in advance!


  Rev. Lang. By When Δ Comment
en1 English drunk_philosopher 2019-05-26 09:59:20 536 Initial revision (published)