Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | arbore9.in, arbore9.out | Sursă | FMI No Stress 10 |
| Autor | Alexandra Udristoiu | Adăugată de |  FMI No Stress 9 •fminostress9 |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 32768 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arbore9
X vrea să facă o excursie într-un oraş în formă de arbore cu N noduri. Pentru fiecare muchie de la u la v se cunosc coeficientul de frumuseţe a al parcurgerii muchiei de la u la v şi coeficientul de frumuseţe b al parcurgerii muchiei de la b la a ( a şi b numere întregi). X poate merge oricum pe muchiile arborelui, însă la final îşi va aduce aminte numai ultima dată când a vizitat o muchie. Coeficientul total este suma coeficienţilor muchiilor pe care X îşi aminteşte că le-a vizitat. Pentru a se hotărî din ce nod să înceapă excursia, X te roagă să afli coeficientul total maxim care se poate obţine plecând din fiecare nod din cele N.
Date de intrare
Fişierul de intrare arbore9.in conţine pe prima linie numărul N de noduri ale arborelui. Următoarele N-1 vor conţine cate 4 numere reprezentând o muchie: ui, vi, ai, bi.
Date de ieşire
În fişierul de ieşire arbore9.out se vor afişa, pe o singură linie, N numere separate prin câte un spaţiu, al i-lea număr reprezentând costul maxim obţinut plecând din nodul i.
Restricţii
- 1 ≤ N ≤ 100 000
- 1 ≤ ui, vi ≤ N
- -1 000 000 000 ≤ ai, bi ≤ 1 000 000 000
- Pentru 30 de puncte, 1 ≤ N ≤ 1000
- Pentru alte 20 de puncte, 0 ≤ ai, bi ≤ 1 000 000 000
Exemplu
| arbore9.in | arbore9.out |
|---|---|
| 8 1 2 2 2 2 3 0 -5 2 4 -1 3 4 5 5 2 4 6 4 2 1 7 3 1 7 8 -1 -3 | 12 12 10 12 12 12 12 11 |
Explicaţie
Plecând din nodul 1, un drum de coeficient total maxim este: 1 -> 7 -> 1 -> 7 -> 1 -> 2 -> 4 -> 6 -> 4 -> 5 Doar coeficientul muchiilor îngroşate va fi adunat la coeficientul total.
