Cerința

Combatanții ti-au dat acum un arbore ce a prins o nouă viață algoritmică

Se dă un arbore cu n noduri, cu rădăcina în nodul 1. Rădăcina nu este considerată frunză chiar dacă are gradul 1. Fiecare nod are un cost asociat și o stare(activ sau inactiv), la început toate nodurile fiind active.

La o operație putem alege o frunză și schimba starea tuturor nodurilor pe drumul de la rădăcină la frunză.

Scopul este să aflați suma maximă a nodurilor active pe care o putem obține, știind că putem realiza operația dată de câte ori vrem pentru fiecare frunză.

Date de intrare

Programul citește pe prima linie de la tastatură numărul n.

Pe următoarele n-1 linii se vor citi muchiile arborelui, a b reprezentând faptul că există o muchie de la a la b.

Pe următoarea linie se vor citi cele n costuri.

Date de ieșire

Programul va afișa pe ecran suma maximă ce se poate obține.

Restricții și precizări

• 1 ≤ n ≤ 200000
• cele n costuri vor fi cuprinse între -1.000.000.000 și 1.000.000.000
• Pentru 10 puncte, 1 ≤ n ≤ 20
• Pentru 20 de puncte, 1 ≤ n ≤ 1000

Exemplu:

Intrare

5
1 2
1 3
2 4
2 5
1 2 4 -4 -5

Ieșire

7

Explicație

În exemplu putem alege mai întâi nodul 4, care va schimba starea nodurilor 4, 2 și 1. Apoi, alegem nodul 5 care va schimba starea nodurilor 5, 2 și 1. Astfel, nodurile 1, 2 și 3 vor rămâne active, iar suma lor este 7.