Maximum Path Sum in Trees

You are given a tree with n nodes. Each node has an integer value. Your task is to find the maximum sum of values on any simple path in the tree. A simple path is a sequence of nodes in which each pair of consecutive nodes is connected by an edge, and no node is repeated.

The answer can be formulated as:

$$ \max_{u,v \in V} \left( \sum_{w \in \text{path}(u,v)} w_{value} \right) $$

Note that the path may start and end at any nodes and does not have to pass through the root.

inputFormat

The input begins with an integer T representing the number of test cases.

For each test case, the input is given in the following format:

1. An integer n that denotes the number of nodes in the tree.
2. A line containing n space-separated integers representing the node values.
3. n-1 lines each containing two integers u and v, indicating an edge between nodes u and v.

The input is read from standard input (stdin).

outputFormat

For each test case, output a single line containing the maximum sum of values on any simple path in the tree.

The output is printed to standard output (stdout).

## sample

2
3
1 2 3
1 2
1 3
4
4 4 4 4
1 2
2 3
3 4

6
16

</p>