Subtree Sum Queries

You are given a tree with \(N\) nodes numbered from 1 to \(N\). Each node \(i\) has an associated integer value \(a_i\). The tree is given as \(N-1\) edges connecting the nodes. You are to answer \(Q\) queries, where each query provides a node \(r\) and asks you to compute the sum of node values in the subtree rooted at \(r\). The subtree of a node \(r\) includes \(r\) itself and all nodes that are its descendants when the tree is rooted at node 1.

Formally, if we define \(\text{subtree}(r)\) as the set of nodes in the subtree of \(r\), then you need to compute:

[ S(r) = \sum_{i \in \text{subtree}(r)} a_i ]

It is guaranteed that the tree is connected and that node 1 is always the root for the purpose of computing subtrees.

inputFormat

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

N
a1 a2 ... aN
u1 v1
u2 v2
... 
 u{N-1} v{N-1}
Q
r1
r2
... 
rQ

Here:

• \(N\) is the number of nodes in the tree.
• \(a1, a2, \dots, aN\) are the node values.
• Each of the next \(N-1\) lines contains two integers \(u\) and \(v\) indicating there is an edge between nodes \(u\) and \(v\).
• \(Q\) denotes the number of queries.
• Each of the following \(Q\) lines contains a single integer \(r\) representing a query.

outputFormat

For each query, output the sum of the subtree rooted at node \(r\) on a new line. The output should be written to STDOUT.

## sample

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

150
120

</p>