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 \textbf{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.

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 $a_1, a_2, \dots, a_K$ (pentru $K \ge 1$), unde există o muchie între $a_i$ şi $a_{i+1}$ pentru orice $1 \le i < K$.