Имеется дерево из n вершин, где вершина номер i (1≤i≤n) имеет ci монет. Вам следует выбрать такое подмножество вершин, в котором никакие две из них не являются соседними (то есть вершины соединенные ребром), а сумма монет в выбранных вершинах наибольшая.
Первая строка содержит количество вершин n (1≤n≤105) в дереве. Каждая из следующих n−1 строк содержит два числа u и v (1≤u,v≤n), задающих ребро в дереве. Последняя строка содержит n целых неотрицательных чисел c1,...cn — количество монет в вершинах дерева.
Выведите максимально возможную сумму монет в выбранном подмножестве вершин дерева.