Subtree Sum Calculation

You are given a binary tree with n nodes. Each node has an integer value and the tree is rooted at node 1. The tree is given in the form of n-1 edges, where each edge connects two nodes.

Your task is to compute the sum of the values of all nodes in the subtree rooted at each node. For each node i, let \(S_i\) denote the subtree sum including the node itself. This relationship can be expressed as:

\(S_i = v_i + \sum_{j \in children(i)} S_j\)

where \(v_i\) is the value of node i and \(children(i)\) represents the direct descendants of node i in the tree.

The answer for the problem is a list of n integers, where the i-th integer is the subtree sum of node i.

inputFormat

The input is read from standard input and has the following format:

1. The first line contains a single integer n (\(1 \le n \le 10^5\)), denoting the number of nodes in the tree.
2. The second line contains n space-separated integers, where the i-th integer represents the value of node i.
3. Each of the next n-1 lines contains two space-separated integers u and v, denoting an edge between nodes u and v.

outputFormat

Output n space-separated integers on a single line. The i-th integer should be the sum of the values in the subtree rooted at node i.

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

15 2 12 4 5