Fişierul intrare/ieşire:arbore9.in, arbore9.outSursăFMI No Stress 10
AutorAlexandra UdristoiuAdăugată defminostress9FMI No Stress 9 fminostress9
Timp execuţie pe test0.5 secLimită de memorie32768 kbytes
Scorul tăuN/ADificultateN/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 v la u ( 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.inarbore9.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 -> 2 -> 4 -> 5 -> 4 -> 6 -> 4 -> 2 -> 1 -> 7 -> 1 -> 7 Doar coeficientul muchiilor îngroşate va fi adunat la coeficientul total.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?