Sum of Leaf Nodes in a Binary Tree

You are given a binary tree with n nodes where each node has an integer value. Your task is to compute the sum of the node values for all leaf nodes. A node is considered a leaf if it has exactly one connection (i.e. it is connected to only one other node) except for the root (node 1), which is not considered a leaf even if it has one connection.

The input format is as follows: the first line contains the integer n, the number of nodes; the second line contains n space-separated integers representing the node values in order; if n > 1, then the next n - 1 lines each contain two integers that represent an undirected edge between two nodes. For a single-node tree (n = 1), the only node is treated as a leaf.

The answer should be printed as a single integer to stdout.

inputFormat

The input is read from standard input in the following format:

1. An integer n — the number of nodes in the tree.
2. A line with n space-separated integers, representing the values of the nodes (from node 1 to node n).
3. If n > 1, then n - 1 subsequent lines follow, each containing two integers u and v that denote an undirected edge between nodes u and v.

outputFormat

Output a single integer — the sum of the values of all leaf nodes (excluding the root unless n = 1) — printed to standard output.

5
10 20 30 40 50
1 2
1 3
3 4
3 5

110