eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Є дерево із 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 — кількість монет у вершинах дерева.

Вихідні дані

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

Приклад

Вхідні дані #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