Maximum sum on a tree#973
Given a tree with vertices, where the -th vertex (1 \le i \le n) contains c_i coins. Select a subset of vertices such that no two of them are adjacent (i.e., connected by an edge), and the sum of coins in the selected vertices is maximized.
The first line contains the number of vertices (1 \le n \le 10^5) in the tree.
Each of the next n - 1 lines contains two integers and (1 \le u, v \le n), defining an edge in the tree.
The last line contains non-negative integers c_1, \ldots, c_n — the number of coins in each vertex of the tree.
Print the maximum possible sum of coins that can be obtained by selecting a subset of vertices in the tree such that no two selected vertices are adjacent.
Example 1
Example 2