Соревнования
Dynamic programming on Trees - Top Level
Максимальная сумма на дереве
Имеется дерево из n вершин, где вершина номер i (1 ≤ i ≤ n) имеет c[i] монет. Вам следует выбрать такое подмножество вершин, в котором никакие две из них не являются соседними (то есть вершины соединенные ребром), а сумма монет в выбранных вершинах наибольшая.
Входные данные
Первая строка содержит количество вершин n (1 ≤ n ≤ 10^5) в дереве. Каждая из следующих n - 1 строк содержит два числа u и v (1 ≤ u, v ≤ 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