Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | berarii.in, berarii.out | Sursă | Selectie echipe ACM ICPC, UPB 2007 |
| Autor | Mugurel Ionut Andreica | Adăugată de |  Mugurel-Ionut Andreica •mugurelionut |
| Timp execuţie pe test | 5 sec | Limită de memorie | 67583 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Berarii
Oamenii beau foarte multa bere in Romania. Pentru fiecare oras i din cele N orase ale tarii (numerotate de la 1 la N) se cunoaste cantitatea de bere Bi ceruta de locuitorii sai. Pentru a satisface cererea totala, o compania faimoasa producatoare de bere doreste sa infiinteze K berarii in K orase diferite din Romania. De la aceste berarii, berea va fi transportata catre celelalte orase folosind reteaua de strazi existenta. Fiecare strada uneste 2 orase distincte si are o anumita lungime. Datorita inundatiilor recente, reteaua de strazi a Romaniei are structura unui arbore: exista exact un singur drum intre orice pereche de orase. Sa consideram un oras i si o berarie amplasata intr-un oras X, care este cea mai apropiata berarie de X. Costul transportului berii din orasul X in orasul i este dist(i,X)*Bi, unde dist(i,X) este distanta dintre orasul i si orasul X. Compania producatoare de bere doreste sa aleaga amplasarea celor K berarii in asa fel incat costul maxim de transport al berii in orice oras din tara sa fie minim.
Date de intrare
Prima linie a fisierului de intrare berarii.in contine numarul intreg T, reprezentand numarul de teste ce urmeaza. Prima linie a fiecarui test contine 2 numere intregi: N si K. Urmatoarele N linii contin cantitatile de bere cerute in fiecare oras: a i-a din aceste linii contine valoarea Bi. Urmatoarele N-1 linii contin cate 3 numere intregi: A, B si L, avand semnificatia ca exista o strada de lungime L intre orasele A si B.
Date de iesire
Pentru fiecare din cele T teste, in ordinea data in fisierul de intrare, afisati o linie continand valoarea minima posibila pentru costul maxim al transportului berii, in cazul unei amplasari optime a berariilor.
Restrictii
- 1 ≤ N ≤ 100 000
- 1 ≤ K ≤ N
- 1 ≤ Bi ≤ 10 000
- Lungimea oricarei strazi este un numar intreg din intervalul [1, 10 000].
Exemplu
| berarii.in | berarii.out |
|---|---|
| 1 4 2 3 4 2 7 1 2 10 2 3 21 2 4 57 | 42 |
Explicatie
Arborele este prezentat in figura de mai jos. Orasele in care vor fi construite berarii sunt colorate cu galben. Costul maxim al transportului berii, egal cu 42, se obtine intre orasul 3 si beraria amplasata in orasul 2.
