Problems
Maximum sum on a tree
Maximum sum on a tree
Given a tree of $n$ nodes, where each node $i~(1 \le i \le n)$ has $c_i$ coins attached with it. You have to choose a subset of nodes such that no two adjacent nodes (i.e. nodes connected directly by an edge) are chosen and sum of coins attached with nodes in chosen subset is maximum.
\includegraphics{https://static.e-olymp.com/content/90/90bb1bf5eda77c35998a37c2faea86c23525dcfb.gif}
\InputFile
The first line contains the number of vertices $n~(1 \le n \le 10^5)$ in a tree. Each of the next $n - 1$ lines gives two integers $u$ and $v~(1 \le u, v \le n)$ and describes an edge in a tree. The last line contains $n$ positive integers $c_1, ... c_n$ --- the number of coins in tree nodes.
\OutputFile
Print the maximum sum of coins in a chosen subset of tree nodes.
Input example #1
5 1 2 1 3 2 4 2 5 1 5 7 1 2
Output example #1
12
Input example #2
5 1 2 1 3 2 4 2 5 3 7 5 10 1
Output example #2
16