Fişierul intrare/ieşire:	irmcast.in, irmcast.out	Sursă	Selectie echipe ACM ICPC, UPB 2007
Autor	Mugurel Ionut Andreica	Adăugată de	Mugurel-Ionut Andreica •mugurelionut
Timp execuţie pe test	0.125 sec	Limită de memorie	67583 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

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₁, astfel incat fiecare nod frunza din arbore este descendent al exact unui singur nod X din S₁ (aceasta inseamna ca orice nod X din S₁ nu este descendent al unui alt nod Y din S₁). 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.

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.

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.

Restrictii

• 1 ≤ T ≤ 21
• 1 ≤ N ≤ 333
• 1 ≤ K ≤ 10
• 1 ≤ costul oricarei muchii ≤ 10 000

Exemplu

Explicatie

In prima (si singura) runda intermediara, nodul 1 trimite mesaje nodului 6 (cu costul 18) si nodului 2 (cu costul 10). Multimea S₁ 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.

Cum se trimit solutii?