Maximum Root-to-Leaf Path Sum in a Tree

You are given a rooted tree with ( n ) nodes. Each node has an integer value. The tree is described by ( n-1 ) edges, and the root of the tree is always node 1. Your task is to find the maximum sum of node values along any path from the root to a leaf. Formally, if ( P ) is the set of all paths from the root to a leaf, and each path ( \pi \in P ) has a sum ( S(\pi) = \sum_{v \in \pi} \text{value}(v) ), you need to compute:

[ \max_{\pi \in P} ; S(\pi) ]

A leaf is defined as a node that does not have any children (for the root, if it is the only node, it is considered a leaf). The tree is guaranteed to be connected and valid.

This problem requires using depth-first search (DFS) or any other tree traversal technique to compute the answer for each test case.

inputFormat

Input is read from standard input (stdin). The first line contains an integer ( T ), representing the number of test cases. For each test case, the input is formatted as follows:

1. A line containing an integer ( n ) representing the number of nodes in the tree.
2. A line containing ( n ) space-separated integers, where the ( i^{th} ) integer represents the value of node ( i ) (nodes are numbered from 1 to ( n )).
3. ( n-1 ) lines each containing two space-separated integers ( u ) and ( v ) that represent an edge connecting nodes ( u ) and ( v ).

Each test case is processed independently.

outputFormat

For each test case, output a single line on standard output (stdout) that contains one integer: the maximum sum of node values along a path from the root (node 1) to any leaf in the tree.## sample

2
5
1 2 3 4 5
1 2
1 3
2 4
2 5
3
5 10 20
1 2
1 3

8
25