Maximum Subset Sum on a Tree

You are given a tree with (N) nodes labeled from 1 to (N), where each node has an associated positive integer value. Your task is to select a subset of nodes such that no two selected nodes are directly connected by an edge, and the sum of the values of the selected nodes is maximized.

In formal terms, if you select a node (u), then none of its immediate neighbors in the tree can be chosen. The tree is rooted at node 1 and is guaranteed to be connected.

For example, consider a tree with 4 nodes with values [3, 2, 1, 10] and edges (1,2), (1,3), and (1,4). The maximum sum you can obtain by choosing a valid subset of nodes is 13.

inputFormat

The input is read from standard input. The first line contains an integer (N) ((1 \leq N \leq 10^5)) representing the number of nodes in the tree. The second line contains (N) space-separated positive integers, where the (i)-th integer is the value of node (i). The following (N-1) lines each contain two integers (u) and (v) denoting an edge between nodes (u) and (v).

outputFormat

Print a single integer to standard output representing the maximum sum of node values that can be selected under the condition that no two chosen nodes are directly connected.## sample

4
3 2 1 10
1 2
1 3
1 4

13