Help for MST problem

Правка en1, от drunk_philosopher, 2019-05-26 09:59:20

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

https://www.codechef.com/problems/SETELE

Link to Editorial

https://discuss.codechef.com/t/setele-editorial/13549

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. Язык Кто Когда Δ Комментарий
en1 Английский drunk_philosopher 2019-05-26 09:59:20 536 Initial revision (published)