drunk_philosopher's blog

By drunk_philosopher, history, 5 years ago, In English

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!