Задачі
Максимальна сума на дереві
Максимальна сума на дереві
Є дерево із $n$ вершин, де вершина номер $i~(1 \le i \le n)$ має $c_i$ монет. Вам слід обрати таку підмножину вершин, в якій ніякі дві з них не є сусідніми (тобто вершини об’єднані ребром), а сума монет у вибраних вершинах найбільша.
\includegraphics{https://static.e-olymp.com/content/90/90bb1bf5eda77c35998a37c2faea86c23525dcfb.gif}
\InputFile
Перший рядок містить кількість вершин $n~(1 \le n \le 10^5)$ в дереві. Кожен з наступних $n - 1$ рядків містить два числа $u$ і $v~(1 \le u, v \le n)$, які задають ребро в дереві. Останній рядок містить $n$ цілих невід’ємних чисел $c_1, ... c_n$ --- кількість монет у вершинах дерева.
\OutputFile
Виведіть максимально можливу суму монет у вибраній підмножині вершин дерева.
Вхідні дані #1
5 1 2 1 3 2 4 2 5 1 5 7 1 2
Вихідні дані #1
12
Вхідні дані #2
5 1 2 1 3 2 4 2 5 3 7 5 10 1
Вихідні дані #2
16