Subtree Sums on Trees

You are given a tree with n nodes where each node has an associated integer value. The tree is represented as an undirected, acyclic connected graph with n-1 edges and the nodes are labeled from 1 to n. It is guaranteed that node 1 is the root of the tree.

Your task is to compute, for each node i, the sum of the values of all nodes in the subtree rooted at i (including i itself). Formally, if we denote by \(S(i)\) the subtree sum for node i and by \(a_j\) the value of node j, then:

\( S(i) = \sum_{j \in \text{subtree}(i)} a_j \)

Output the subtree sums for nodes 1 through n in order.

inputFormat

The first line contains an integer T denoting the number of test cases.

For each test case, the input is as follows:

• The first line contains an integer n representing the number of nodes in the tree.
• The second line contains n space-separated integers, where the i-th integer represents the value of node i.
• The next n-1 lines each contain two space-separated integers u and v, representing an undirected edge between nodes u and v.

You may assume that the given input always represents a valid tree with node 1 as the root.

outputFormat

For each test case, print a single line containing n space-separated integers. The i-th integer should be the sum of the values in the subtree rooted at node i.

## sample

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

10 2 7 4

</p>