Subtree Sums in a Binary Tree

Given a tree with (N) nodes where each node has an associated integer value, compute the sum of the values in the subtree of each node. The subtree of a node consists of the node itself and all of its descendants when the tree is rooted at node 1. \newline\newline The input consists of (T) test cases. For each test case, you are given an integer (N) (the number of nodes), a line with (N) space-separated integers for the node values (ordered from node 1 to node (N)), and (N-1) subsequent lines each containing two integers (u) and (v) which denote an edge between nodes (u) and (v). \newline\newline Your task is to compute and output the subtree sum for each node in the order of their labels.

inputFormat

The input begins with an integer (T), the number of test cases. For each test case, the input is structured as follows: \newline\newline 1. A single integer (N) indicating the number of nodes in the tree. \newline\newline 2. A line containing (N) space-separated integers representing the values of nodes 1 through (N). \newline\newline 3. (N-1) lines each containing two integers (u) and (v) representing an edge between nodes (u) and (v).

outputFormat

For each test case, output one line containing (N) space-separated integers. The (i)th integer should represent the sum of the values in the subtree rooted at node (i) (with the tree rooted at node 1).## sample

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

16 3 8
15 14 8 4 5