Revizia anterioară Revizia următoare
Fişierul intrare/ieşire: | simulare.in, simulare.out | Sursă | Concursul National de Informatica "Adolescent Grigore Moisil" 17 |
Autor | Chichirim George | Adăugată de | AGMInformatica •AGMinformatica |
Timp execuţie pe test | 0.3 sec | Limită de memorie | 262144 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Simulare
Deoarece anul trecut nu ati reusit sa-l ajutati pe Hektor sa treaca bacul, el este nevoit sa-l dea si anul acesta. Vreme trece, vreme vine si s-au apropiat simularile. Anul trecut, Hektor nu a invatat pentru simularea la romana pentru ca a zis atunci ca mult mai este pana la bac si ca are timp destul sa invete (evident, acesta s-a inselat). Tara in care locuieste Hektor are forma unui arbore cu noduri. Deoarece acesta este un interlop cu relatii internationale, el cunoaste cate o profesoara de romana in fiecare nod al tarii care ii poate da cate un comentariu de invatat pentru simulare. Fiecare comentariu este caracterizat de doua numere si , reprezentand shukarimea comentariului (frumusetea acestuia cat si valoarea sa stilistica), iar reprezentand efortul necesar de a-l toci. Mai sunt fix zile pana la simulare, iar Hektor isi stie progrmul struna. Pentru fiecare zi din cele , el are niste afaceri de indeplinit, astfel acesta fiind nevoit sa se deplaseze din nodul in nodul . Deoarece, anul acesta, Hektor este pus pe invatat, ci nu numai pe afaceri murdare, el ar vrea sa stie care e shukarimea maxima totala pe care ar putea sa o obtina daca el ar putea lua niste comentarii de pe drumul de la nodul la nodul cu proprietatea ca efortul lor de invatare total este cel mult egal cu (el isi devota putin timp pentru a invata, dar totusi are si niste afaceri mult mai importante de rezolvat si nu isi permite sa se oboseasca prea tare cu invatatul).
Date de intrare
Fişierul de intrare simulare.in contine pe prima linie numerele N si M. Pe urmatoarele N linii se afla cate doua numere naturale si ce reprezinta shukarimea si efortul de invatare al comentariului din nodul i. Pe urmatoarele N-1 linii se afla cate doua numere naturale x si y cu semnificatia ca exista o muchie intre nodurile x si y. Pe urmatoarele M linii se afla cate trei numere naturale , si .
Date de ieşire
În fişierul de ieşire simulare.out trebuie sa se afle M linii, pe linia i fiind suma shukarimii maxima posibila a unei submultimi de comenatrii de pe drumul de la nodul la nodul cu propietatea ca suma eforturilor acestora este mai mica sau egala cu .
Restricţii
- 1 ≤ N ≤ 2000
- 1 ≤ M ≤ 20000
- 1 ≤ ≤ 1000
- 1 ≤ ≤ 1.000.000
Exemplu
simulare.in | simulare.out |
---|---|
10 6 5 5 3 9 4 4 10 1 3 1 8 10 1 5 1 1 1 9 5 7 10 7 9 7 5 9 3 10 4 5 8 10 1 5 6 1 2 1 8 7 10 1 5 14 1 4 12 1 1 18 6 9 20 6 1 14 | 6 8 18 5 16 8 |