eolymp
Змагання

Dynamic programming on Trees - Top Level

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

Є дерево із n вершин, де вершина номер i (1 ≤ i ≤ n) має ci монет. Вам слід обрати таку підмножину вершин, в якій ніякі дві з них не є сусідніми (тобто вершини об’єднані ребром), а сума монет у вибраних вершинах найбільша.

prb973.gif

Вхідні дані:

Перший рядок містить кількість вершин  n (1n105) в дереві. Кожен з наступних n - 1 рядків містить два числа u і v (1u, vn), які задають ребро в дереві. Останній рядок містить n цілих невід’ємних чисел c1, ... cn – кількість монет у вершинах дерева.

Вихідні дані:

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB
Вхідні дані #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