e-olymp
Соревнования

Dynamic programming on Trees - Top Level

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

Имеется дерево из 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