Distanţa dintre două noduri ale arborelui este egală cu suma costurilor muchiilor de pe cel mai scurt drum dintre cele două noduri.
Se defineşte valoarea unui arbore ca fiind suma distanţelor dintre oricare 2 noduri ale acestuia.
Petrică are la dispoziţie următoarea operaţie, pe care o poate face *o singură dată*: alege un lanţ al arborelui şi înjumătăţeşte costul tuturor muchiilor de pe acel lanţ. Ajutaţi-l să găsească cea mai mică valoare a unui arbore obţinut după aplicarea operaţiei.

Un lanţ se defineşte ca fiind o înşiruire de noduri distincte <tex>a_1, a_2, \dots, a_K</tex> (pentru <tex>K \ge 1</tex>), unde există o muchie între <tex>a_i</tex> şi <tex>a_{i+1}</tex> pentru orice <tex>1 \le i < K</tex>.
h2. Date de intrare

h2. Date de ieşire

În fişierul de ieşire $halftree.out$ ...

În fişierul de ieşire $halftree.out$ se va afişa pe primul rând un număr întreg reprezentând valoarea minimă a unui arbore obţinută după aplicarea operaţiei asupra arborelui iniţial.

h2. Restricţii