Maximum Sea Star Collection

Little Ming wants to catch sea stars from the ocean floor. The ocean floor is represented as a tree with n nodes labeled from 1 to n, and each node i carries a weight p_i. A sea star is defined as a flower subgraph (or star) in the tree. Formally, if we choose a node as the center O and a nonempty subset of its directly connected neighbors as leaf nodes a₁, a₂, ..., a_t, then the sea star's value is given by

\( |p_O - \sum_{i=1}^{t} p_{a_i}| \)

The collection of sea stars must be vertex-disjoint (i.e. no two sea stars share any node). The task is to select a set of sea stars so that the total collected value is maximized.

Additional Definitions:

• Flower Graph: A connected graph with diameter at most three. In this graph the node with the highest degree is called the center, and all other nodes (which have degree one in the subgraph) are the leaves. In particular, the smallest flower graph is a simple edge connecting two nodes.

Your task is to compute the maximum total value of sea stars that can be collected from the tree.

inputFormat

The first line contains an integer n (n ≥ 1), representing the number of nodes in the tree.

The second line contains n integers: p₁, p₂, ..., p_n, where p_i is the weight of node i.

Each of the following n - 1 lines contains two integers u and v (1 ≤ u, v ≤ n), representing an undirected edge between nodes u and v.

outputFormat

Output a single integer: the maximum total value of sea stars that can be collected, subject to the condition that no two sea stars share a node.

sample

3
5 3 2
1 2
1 3

3