Subtree Sums in a Tree

You are given a tree with n nodes, rooted at node 1. Each node has an integer value. Your task is to compute the subtree sum for each node. The subtree sum of a node is defined as the sum of the values of all the nodes in its subtree (including the node itself). Formally, for each node i, the subtree sum is given by:

$$ S_i = a_i + \sum_{c \in \text{children}(i)} S_c $$

where a_i is the value of node i and S_c is the subtree sum of a child c of node i.

Read the input from standard input and write the result to standard output.

inputFormat

The input begins with an integer T (T ≥ 1), the number of test cases. Each test case is described as follows:

1. An integer n (1 ≤ n ≤ 200000), the number of nodes in the tree.
2. A line with n space-separated integers, representing the values of the nodes in order from 1 to n.
3. For the next n - 1 lines, each line contains two space-separated integers u and v representing an undirected edge between nodes u and v.

It is guaranteed that the given edges form a tree (i.e. a connected acyclic graph). For each test case, node 1 is the root of the tree.

outputFormat

For each test case, output one line containing n space-separated integers, where the i-th integer is the subtree sum of node i.

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

15 11 3 4 5