Maximum Subtree Sum

You are given a tree with n nodes where each node has an integer value. The tree is provided as a list of node values and n-1 edges connecting the nodes. A subtree is defined as any connected component of the tree. Your task is to find the maximum sum of node values over all possible subtrees.

In other words, if you choose any node and consider the connected set of nodes (by traversing via edges without revisiting any node), compute the sum of their values. Among all these connected subtrees, output the maximum sum.

You may assume that the tree is connected. All nodes are numbered from 1 to n.

The maximum subtree sum can be expressed mathematically as:

$$\max_{S \subseteq V \; \text{and } S \text{ is connected}} \left\{ \sum_{v \in S} a_v \right\}, $$

where \( a_v \) is the value of node \( v \).

inputFormat

The input is read from standard input and has the following format:

n
v1 v2 v3 ... vn
u1 v1
u2 v2
... (n-1 lines of edges)

Here, n is the number of nodes; the second line contains n space-separated integers representing the node values; and each of the next n-1 lines contains two integers representing an edge between two nodes (nodes are 1-indexed).

outputFormat

Output to standard output a single integer: the maximum subtree sum.

## sample

5
1 0 1 1 0
1 2
1 3
2 4
2 5

3