Maximum Weighted Independent Set on a Tree with Distinct Depths

Given a tree with root (1) and each node (i) having a weight (V_i), select a set of nodes ({P_i}) such that:

1. No two selected nodes are adjacent.
2. The distances from the root of any two selected nodes are distinct.
3. The sum of the weights of the selected nodes is maximized.

Formally, if the distance from the root to a node (v) is denoted by (d(v)) (with (d(1)=0)), then for any two selected nodes (P_x) and (P_y) the conditions must hold:

• (P_x) and (P_y) are not directly connected (i.e. there is no edge between them).
• (d(P_x) \neq d(P_y)).

Output the maximum sum of weights possible by selecting such a set of nodes.

inputFormat

The first line contains an integer (n) ( (1 \le n \le 10^5)) -- the number of nodes in the tree.

The second line contains (n) integers (V_1, V_2, \ldots, V_n), where (V_i) is the weight of node (i).

Each of the next (n-1) lines contains two integers (u) and (v) denoting an undirected edge between nodes (u) and (v). It is guaranteed that the graph forms a tree and the root of the tree is node (1).

Note: The distance of a node is defined as the number of edges from the root node (1) to that node. Thus, (d(1)=0).

outputFormat

Output a single integer: the maximum sum of weights of a set of nodes satisfying the conditions.

sample

1
5

5