Binary Tree Traversal Sum

You are given a rooted binary tree with N nodes. Each node has an integer value. The tree is constructed using N node values and N-1 edges. The construction rules are as follows: nodes are numbered from 1 to N, and for each edge (u, v), if the node u does not have a left child then node v becomes its left child; otherwise, node v becomes its right child.

Your task is to compute the sum of all node values by performing three different depth-first traversals: Inorder, Preorder, and Postorder. During each traversal, every node’s value is added exactly once, so the sums will be identical. However, you need to output the three sums separated by a space.

The mathematical representation of the sum is given by:

\( S = \sum_{i=1}^{N} a_i \)

where \( a_i \) is the value of the i-th node.

inputFormat

Input Format:

• The first line contains an integer N, the number of nodes in the binary tree.
• The second line contains N space-separated integers representing the node values from node 1 to node N.
• The next N-1 lines each contain two integers u and v indicating an edge from node u to node v.

Note: The input is provided through standard input (stdin).

outputFormat

Output Format:

Print three space-separated integers representing the sums of node values for the Inorder, Preorder, and Postorder traversals respectively. The output should be written to standard output (stdout).

## sample

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

15 15 15