Maximum Energy Path in a Tree

You are given a tree with \( n \) nodes where each node has an energy level. The tree is defined by \( n-1 \) edges. Your task is to compute the maximum possible sum of energy levels along any simple path in the tree. A path is defined as a sequence of nodes with each adjacent pair connected by an edge. Note that if all energy levels are negative, the answer is simply the maximum (least negative) energy level among all nodes.

The problem can be formulated as follows. Let \( E_i \) be the energy at node \( i \) (\(1 \le i \le n\)). Find the maximum value of \( \sum_{j \in P} E_j \) over all paths \( P \) in the tree.

inputFormat

The input is given in the following format from stdin:

• The first line contains an integer \( n \) — the number of nodes.
• The second line contains \( n \) space-separated integers — the energy levels of the nodes.
• Each of the next \( n-1 \) lines contains two space-separated integers \( u \) and \( v \), representing an edge between nodes \( u \) and \( v \).

outputFormat

Output a single integer to stdout — the maximum sum of energy levels along any path in the tree.

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

10