Maximum Sum Path in a Tree

Given a tree with ( n ) nodes where each node has an associated integer value, your task is to determine the maximum possible sum along any simple path in the tree. A simple path is a sequence of nodes where no node appears more than once. Formally, if ( P ) is any simple path in the tree, you are to compute ( \max_{P} \sum_{v \in P} value(v) ).

The input consists of multiple test cases. Each test case begins with an integer ( n ) indicating the number of nodes. The next line contains ( n ) integers representing the value of each node (the first value corresponds to node 1, the second to node 2, and so on). This is followed by ( n-1 ) lines each containing two integers ( u ) and ( v ) representing an undirected edge between nodes ( u ) and ( v ). A test case with ( n = 0 ) signals the end of input.

inputFormat

The input is read from standard input (stdin) and consists of one or multiple test cases. Each test case is structured as follows:

1. A single integer ( n ) (( 1 \leq n \leq 10^5 ), for example) representing the number of nodes in the tree. A value of 0 indicates the end of input.
   
2. A line with ( n ) integers denoting the values associated with nodes 1 through ( n ).
   
3. ( n-1 ) lines each containing two integers ( u ) and ( v ), representing an undirected edge connecting nodes ( u ) and ( v >.

outputFormat

For each test case, output a single line to standard output (stdout) containing the maximum sum along any simple path in the tree.## sample

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

21