CSES - Pienin virittävä puu

Tarkastellaan seuraavaa suuntaamatonta verkkoa:

  • Verkossa on solmut 1,2,\dots,N ja N=1000.
  • Jokaisen solmuparin välillä on kaari. Solmujen a ja b välisen kaaren paino on \min(a,b).

Kuinka painava on verkon pienin virittävä puu?

Perustele lyhyesti vastauksesi: