Максимальна сума на дереві

Дано дерево з $n$ вершинами, де вершина з номером $i(1\le i\le n)$ містить $c_i$ монет. Виберіть таку підмножину вершин, щоб жодні дві з них не були суміжними (тобто не з'єднані ребром), а сума монет у вибраних вершинах була максимальною.

Вхідні дані

Перший рядок містить кількість вершин $n(1\le n\le 10^5)$ у дереві. Кожен з наступних $n-1$ рядків містить два числа $u$ і $v(1\le u,v\le n)$, які задають ребро в дереві. Останній рядок містить $n$ невід'ємних цілих чисел $c_1,...c_n$ — кількість монет у кожній вершині дерева.

Вихідні дані

Виведіть максимально можливу суму монет, яку можна отримати, вибравши підмножину вершин дерева за умови відсутності суміжних вершин.

Приклади