e-olymp
Задачі

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

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

Имеется дерево из n вершин, где вершина номер i (1in) имеет ci монет. Вам следует выбрать такое подмножество вершин, в котором никакие две из них не являются соседними (то есть вершины соединенные ребром), а сумма монет в выбранных вершинах наибольшая.

prb973.gif

Входные данные

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

Выходные данные

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

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