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

Poveste şi cerinţă...

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: x_i, y_i, a_i, b_i, unde x_i şi y_i sunt nodurile, a_i reprezintă costul parcurgerii muchiei de la x la y şi b_i reprezintă costul parcurgerii muchiei de la y la x.

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 ≤ x_i, y_i ≤ N
• -1 000 000 000 ≤ a_i, b_i ≤ 1 000 000 000
• Pentru 30 de puncte, 1 ≤ N ≤ 1000
• Pentru alte 20 de puncte, 0 ≤ a_i, b_i ≤ 1 000 000 000

Exemplu

Explicaţie

Plecând din nodul 1, un drum de coeficient total maxim este: 1 -> 7 -> 1 -> 7 -> 1 -> 2 -> 4 -> 6 -> 4 -> 5

Cum se trimit solutii?