== include(page="template/taskheader" task_id="irmcast") ==
Sa consideram o retea de comunicatie ce consta din $N$ noduri numerotate de la $1$ la $N$. Nodurile sunt interconectate in asa fel incat reteaua are structura unui arbore avand radacina in nodul $1$. Nodul $1$ doreste sa trimita un mesaj (acelasi mesaj) catre fiecare nod care este o frunza in arbore (adica nu are nici un fiu) - aceasta operatie este cunoscuta sub numele de *multicast*. Un mesaj poate fi transmis numai de la un nod la unul din descendentii acestuia (inclusiv nodul insusi). Fiecare muchie a arborelui are asociat un cost, iar costul transmiterii unui mesaj de la un nod $X$ la unul din descendentii acestuia este suma costurilor muchiilor de pe drumul unic de la $X$ la $Y$ (daca $X = Y$, atunci costul este $0$). Costul total al unei strategii de multicast este egal cu suma costurilor transmiterii fiecarui mesaj.
Pentru a-si indeplini scopul, nodul $1$ va utiliza urmatoarea strategie de multicast: Strategia consta din $K$ runde intermediare. In prima runda, nodul $1$ trimite un mesaj individual catre o submultime de noduri $S{~1~}$, astfel incat fiecare nod frunza din arbore este descendent al exact unui singur nod $X$ din $S{~1~}$ (aceasta inseamna ca orice nod $X$ din $S{~1~}$ nu este descendent al unui alt nod $Y$ din $S{~1~}$). In runda $i$ {$(2 ≤ i ≤ K)$}, fiecare nod X din $S{~i-1~}$ trimite un mesaj individual unei submultimi de noduri $S{~i,X~}$ din subarborele sau, in asa fel incat fiecare nod frunza care este descendent al lui $X$ este descendent al exact unui singur nod din $S{~i,X~}$. Submultimea de noduri $S{~i~}$ este reuniunea multimilor $S{~i,X~}$, pentru fiecare $X$ din $S{~i-1~}$. La final, fiecare nod $X$ din $S{~K~}$ trebuie sa trimita un mesaj individual fiecarui nod frunza care este descendent al lui $X$.
Fiind data reteaua de comunicatie, costul fiecarei muchii si numarul de runde intermediare $K$, determinati costul total minim al unei strategii de multicast.
Poveste si cerinta...
h2. Date de intrare
Prima linie a fisierului de intrare $irmcast.in$ contine numarul intreg $T$, reprezentand numarul de teste ce urmeaza. Prima linie a fiecarui test contine $2$ numere intregi, separate printr-un spatiu, $N$ si $K$. Urmatoarele $N-1$ linii contin cate $3$ numere intregi fiecare: $A$, $B$ si $C$, avand semnificatia ca nodul $B$ este un fiu al nodului $A$, iar muchia $(A,B)$ are costul $C$.
...
h2. Date de iesire
Pentru fiecare din cele $T$ teste date in fisierul de intrare, afisati in fisierul de iesire $irmcast.out$ cate o linie continand costul total minim al unei strategii de multicast avand proprietatile specificate.
...
h2. Restrictii
* $1 ≤ T ≤ 21$
* $1 ≤ N ≤ 333$
* $1 ≤ K ≤ 10$
* $1 ≤ costul oricarei muchii ≤ 10 000$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. irmcast.in |_. irmcast.out |
|1
6 1
1 2 10
1 3 11
2 4 21
2 5 17
3 6 7
|66
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicatie
In prima (si singura) runda intermediara, nodul $1$ trimite mesaje nodului $6$ (cu costul $18$) si nodului $2$ (cu costul $10$). Multimea $S{~1~}$ este ${2,6}$. La final, nodul $6$ va trimite un mesaj catre el insusi (cu costul $0$), iar nodul $2$ va trimite mesaje nodului $4$ (cu costul $21$) si nodului $5$ (cu costul $17$). Costul total este $18+10+21+17=66$.
!problema/irmcast?irmcast.jpg!
...
== include(page="template/taskfooter" task_id="irmcast") ==
