Proof of O(1) solution to I would walk 500 miles

Problems and Contests
#1

Does anyone know how to prove the math solution for I would walk 500 miles?
solution link: https://usaco.guide/solutions/usaco-946#solution-3.

#2

The two lowest-weight edges of the MST are (N-1,N) and (N-2,N). Can you figure it out from there?

2 Likes
#3

Hi, would you mind explaining a bit further? Can’t quite wrap my mind around it.

#4

What other edges are part of the MST? (If you don’t know, perhaps write a program to print them out.)

#5

Hi, I have since written up a full editorial for the \mathcal{O}(1) solution: https://usaco.guide/solutions/usaco-946
Hope it can be of some use!