SOLINFO.ro Runda 4 | CosGigMax

Doi prieteni, Gigel și Costel, plictisiți după ce au terminat de citit poveștile „Guguștiucului cel Împiedicat", s-au gândit la următoarea problemă: Se dă un arbore cu $N$ noduri, fiecare nod din arbore având câte o valoare pe nod. Gigel îi propune lui Costel să afle pentru un nod dat, care este suma maximă a unui lanț care trece prin nodul respectiv. Costel imediat își dă seama că problema e foarte usoară, așa că, el fiind încrezut, crede că o va putea rezolva pentru toate nodurile din arbore! Gândindu-se puțin, a realizat că are nevoie de ajutorul vostru pentru a nu se face de râs în fața prietenului său!

Cerință

Ajutați-l pe Costel să găsească pentru fiecare nod din arbore costul maxim al unui lanț care trece prin nodul respectiv! Un arbore cu $N$ noduri este un graf conex aciclic cu $N - 1$ muchii. Un lanț este o listă de noduri astfel încât fiecare nod din arbore apare cel mult o dată, iar între fiecare două noduri vecine în listă există muchie între ele. Mulțimea nodurilor unui lanț nu poate să fie vidă. Costul unui lanț reprezintă suma valorilor nodurilor din lanțul curent.

Date de intrare

Pe prima linie din fișierul de intrare se va afla numărul $N$, care reprezintă numărul de noduri din arbore.
Pe următoarele $N - 1$ linii se vor afla câte două numere: $x_i$ și $y_i$, care semnifică faptul că există muchie între nodurile $x_i$ și $y_i$.
Pe linia $N + 1$ se vor afla $N$ valori, unde $v_i$ reprezintă valoarea nodului $i$.

Date de ieșire

Pe prima linie a fișierului de ieșire se vor afișa $N$ valori, unde a $i$-a valoare reprezintă răspunsul pentru nodul $i$. Răspunsurile vor fi afișate cu un spațiu între ele.

Restricții

• $1 \leq N \leq 10^5$
• $-10^9 \leq v_i \leq 10^9$
• Se recomandă utilizarea tipului de date long long.

Exemplu

cosgigmax.in

10
1 2
1 5
1 7
2 4
2 3
7 6
7 8
6 10
6 9
2 -5 -2 3 3 1 4 -10 -8 -7

cosgigmax.out

10 5 0 5 10 10 10 -1 2 3