Balaurii
sunt binecunoscuti pentru neplacerile pe care le provoaca participantilor la
concursurile de informatica. In trecut, acestia mancau aproximativ jumatate
dintre participanti, insa pe masura ce informaticienii au devenit mai inteligenti,
balaurii ii ataca in alte moduri, in special ca personaje in cadrul unor probleme
neplacut de grele. Unul dintre balauri, cunoscut ca balaurul cu M
capete, a decis sa devina vegetarian (dupa multe incercari esuate de a-si satisface
foamea prinzand informaticieni). Mai exact, el doreste sa manance toate cele
N mere aflate in cele N
noduri ale unui arbore. Nodurile arborelui sunt numerotate de la 1
la N, iar radacina acestuia este
nodul 1. Marul din radacina arborelui
este numit "marul de aur" (datorita calitatilor sale magice de a creste
insutit inteligenta celui care mananca din el). Merele din celelalte N-1
noduri sunt mere obisnuite.
Dintre cele M capete ale balaurului,
primul cap este "capul principal", iar celelalte sunt "capete
secundare". Capul principal, fiind mai destept si mai dezvoltat, trebuie
sa manance exact K mere, printre
care si marul de aur. Fiecare din celelalte M-1
capete trebuie sa manance cel putin un mar, in asa fel incat toate merele sa
fie mancate.
Daca doua mere situate in 2 noduri adiacente din arbore sunt mancate de acelasi
cap, atunci capul respectiv va trebui sa manance si muchia dintre cele 2 mere.
Pentru fiecare muchie se cunoaste cantitatea de indigestie pe care i-o provoaca
balaurului, in caz ca aceasta este mancata de vreun cap. Indigestia totala a
balaurului este egala cu suma cantitatilor de indigestie ale muchiilor arborelui
mancate de catre capetele acestuia.
Cerinta
Scrieti
un program care determina indigestia totala minima astfel incat toate conditiile
mentionate sa fie indeplinite.
Date de intrare
Prima linie a fisierului
de intrare balaur.in contine
3 numere intregi, separate prin cate un spatiu: N,
M si K.
Urmatoarele N-1 linii contin
cate 3 numere intregi, separate
prin cate un spatiu: a, b
si x unde a
si b reprezinta 2 noduri adiacente
in arbore, iar x reprezinta cantitatea
de indigestie asociata muchiei respective.
Date de iesire
In fisierul de iesire balaur.out
veti afisa indigestia totala minima. Daca balaurul nu poate manca merele astfel
incat sa fie indeplinite toate conditiile cerute, afisati -1.
Restrictii si precizari
1 <= N <= 300
2 <= M <= N
1 <= K <= N
Cantitatea de indigestie
asociata fiecarei muchii este un numar natural din intervalul [0,105].
In
figura se poate vedea arborele din exemplu, avand N=8
noduri (fiecare continand cate un mar) si N-1=7
muchii. Cantitatile de indigestie sunt scrise pe muchii. Considerand ca
balaurul are M=2 capete,
iar capul principal trebuie sa manance exact K=4
mere, determinam indigestia totala minima ca fiind egala cu 4.
Aceasta valoare se obtine in cazul in care capul principal mananca merele
aflate in nodurile marcate cu negru din a doua figura, iar cel de-al doilea
cap mananca merele din nodurile marcate cu alb. Este inghitita o singura
muchie, de catre capul principal, care are cantitatea de indigestie egala
cu 4.
As.drd.ing.
Mugurel Ionut Andreica
Universitatea Politehnica Bucuresti, Facultatea de Automatica si Calculatoare mugurel_ionut@yahoo.com
