== include(page="template/taskheader" task_id="paths") ==

Portocal, pisica cea portocalie, a găsit un arbore (graf neorientat conex aciclic) cu $N$ noduri numerotate de la $1$ la $N$. Pe fiecare muchie $i$ ($1 &le i < N$) care conectează nodurile $x{~i~}$ şi $y{~i~}$ se află $c{~i~}$ gustări pentru pisici.

Portocal, pisica cea portocalie, a găsit un arbore (graf neorientat conex aciclic) cu $N$ noduri numerotate de la $1$ la $N$. Pe fiecare muchie $i$ ({$1 &le; i < N$}) care conectează nodurile $x{~i~}$ şi $y{~i~}$ se află $c{~i~}$ gustări pentru pisici.

Portocal poate alege exact $K$ nodurii; pentru fiecare dintre nodurile alese, el va merge pe drumul de la rădăcina arborelui la nodul ales şi va mânca gustările de pe muchiile pe care trece. Evident, el poate mânca gustările de pe o muchie o singură dată. Deoarece Portocal este o pisică foarte curioasă din fire, el ar vrea să afle care este numărul maxim de gustări pe care le poate mânca, alegând optim cele $K$ noduri, dacă rădăcina arborelui era nodul $i$, pentru fiecare $i$ de la $1$ la $N$.

* $1 ≤ K ≤ N ≤ 100 000$
* $0 ≤ c{~i~} ≤ 1 000 000 000$
* Pentru $8$ puncte, $N ≤ 18$

* Pentru $11$ puncte, $N ≤ 200$ şi $K ≤ 20$
* Pentru $17$ puncte, $N ≤ 1000$ şi $K ≤ 100$

* Pentru $12$ puncte, $N ≤ 200$ şi $K ≤ 20$
* Pentru $16$ puncte, $N ≤ 1000$ şi $K ≤ 100$

* Pentru $20$ puncte, $N ≤ 2000$
* Pentru $12$ puncte, $K = 1$

Dacă rădăcina este nodul $1$, atunci Portocal poate alege nodurile $4$, $6$ şi $9$. Drumurile de la rădăcină la nodurile alese vor fi $1 − 2 − 3 − 4$, $1 − 2 − 6$, $1 − 7 − 9$ şi numărul total de gustări de pe aceste drumuri va fi $5 + 3 + 4 + 5 + 6 + 5 = 28$. A se observa că gustările de pe muchia $1 − 2$ au fost adunate o singură dată.

== include(page="template/footer" task_id="paths") ==

== include(page="template/taskfooter" task_id="paths") ==