Maximum Sum Path in a Tree

Given a tree rooted at node 1 with (N) nodes, where each node (i) has a value (a_i), your task is to determine the maximum sum along any path from the root to a leaf. Here, a leaf is defined as a node that does not have any children when the tree is viewed as rooted at node 1. The sum along a path is given by (\sum_{i \in path} a_i).

You will be given (T) test cases. For each test case, output the maximum sum of values along a path from the root (node 1) to any leaf.

inputFormat

Input is provided via standard input (stdin). The first line contains an integer (T), the number of test cases. For each test case, the following input is provided:

1. An integer (N) representing the number of nodes in the tree.
2. A line with (N) space-separated integers, where the (i)th integer is the value (a_i) of node (i).
3. (N-1) lines each containing two integers (u) and (v), representing an undirected edge between nodes (u) and (v).

Note: The tree is rooted at node 1.

outputFormat

For each test case, output a single integer (on a new line) which is the maximum sum of values along a path from the root to any leaf.## sample

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

4
10