Maximum Beauty Sum Subtree

Given a tree of N nodes and N-1 edges where each node (flower) has a beauty index (which can be positive or negative), you are allowed to perform a series of "pruning" operations. A pruning operation consists of removing one edge, which splits the tree into two connected subtrees. You then discard one of the two subtrees. After a series of such operations (possibly zero), only one connected subtree remains. Your task is to determine the maximum possible sum of the beauty indices of the remaining subtree.

Note: Any connected subgraph of a tree is also a tree. Essentially, the problem reduces to finding a connected subtree with maximum sum of node values.

Input Format: The first line contains an integer N denoting the number of flowers. The second line contains N space-separated integers denoting the beauty indices of the flowers. Each of the next N-1 lines contains two integers u and v which indicate that there is an edge between the uth and the vth flower. It is guaranteed that the graph is a tree.

Mathematical Formulation: Let the tree be represented by a set of nodes \(V\) and edges \(E\). For each node \(i \in V\), let the beauty index be \(b_i\). Find a connected subset \(S \subseteq V\) that maximizes \(\sum_{i \in S} b_i\).

inputFormat

The input consists of multiple lines:

1. The first line contains an integer N (1 ≤ N ≤ 10⁵), the number of flowers.
2. The second line contains N integers, representing the beauty indices of the flowers. These integers can be negative.
3. The next N-1 lines each contain two integers u and v (1-indexed), indicating that there is an edge between flower u and flower v.

outputFormat

Output a single integer, the maximum possible sum of beauty indices of a connected subtree that can be obtained through a series of pruning operations.

If all beauty indices are negative, output the maximum (least negative) one.

sample

5
1 2 3 -2 -1
1 2
1 3
2 4
2 5

6