Имеется дерево из вершин, где вершина номер имеет монет. Вам следует выбрать такое подмножество вершин, в котором никакие две из них не являются соседними (то есть вершины соединенные ребром), а сумма монет в выбранных вершинах наибольшая.
Первая строка содержит количество вершин в дереве. Каждая из следующих строк содержит два числа и , задающих ребро в дереве. Последняя строка содержит целых неотрицательных чисел — количество монет в вершинах дерева.
Вывести максимально возможную сумму монет в выбранном подмножестве вершин дерева.