Priority Roads

You are given a tree with n towns (nodes) numbered from 0 to n-1 and very busy roads connecting these towns. Each road directly connects two different towns. The town populations are given in an array. For each road, compute the sum of the populations of the two towns it directly connects.

Input Constraints:

• \(2 \le n \le 10^5\)
• Population of each town is an integer; the population array has size \(n\).
• There are exactly \(n - 1\) roads, and each road is represented by two integers \(a\) and \(b\) (with \(0 \le a,b < n\)) denoting a connection between town \(a\) and town \(b\).

The input is provided via standard input (stdin) and your output must be printed to standard output (stdout). The answer for each road should be printed in the same order as the roads are input, with the sums separated by spaces.

inputFormat

The first line contains an integer \(n\), the number of towns. The second line contains \(n\) space-separated integers representing the population of each town. The next \(n - 1\) lines each contain two integers \(a\) and \(b\), indicating a road connecting town \(a\) and town \(b\).

outputFormat

Output a single line containing \(n - 1\) space-separated integers, where each integer is the sum of the populations of the two towns connected by the corresponding road.

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

3 5 6 9