Məsələlər
Максимальная сумма на дереве
Максимальная сумма на дереве
Имеется дерево из $n$ вершин, где вершина номер $i~(1 \le i \le n)$ имеет $c_i$ монет. Вам следует выбрать такое подмножество вершин, в котором никакие две из них не являются соседними (то есть вершины соединенные ребром), а сумма монет в выбранных вершинах наибольшая.
\includegraphics{https://static.e-olymp.com/content/90/90bb1bf5eda77c35998a37c2faea86c23525dcfb.gif}
\InputFile
Первая строка содержит количество вершин $n~(1 \le n \le 10^5)$ в дереве. Каждая из следующих $n - 1$ строк содержит два числа $u$ и $v~(1 \le u, v \le n)$, задающих ребро в дереве. Последняя строка содержит $n$ целых неотрицательных чисел $c_1, ... c_n$ --- количество монет в вершинах дерева.
\OutputFile
Вывести максимально возможную сумму монет в выбранном подмножестве вершин дерева.
Giriş verilənləri #1
5 1 2 1 3 2 4 2 5 1 5 7 1 2
Çıxış verilənləri #1
12
Giriş verilənləri #2
5 1 2 1 3 2 4 2 5 3 7 5 10 1
Çıxış verilənləri #2
16