Subtree Strength Calculation

You are given a tree with N nodes, where each node i has a strength value represented by an integer A[i]. The tree is provided as an undirected graph with N − 1 edges. You are also given Q queries. In each query, you are asked to calculate the total strength of the subtree rooted at a given node. The strength of a subtree is the sum of the strengths of all nodes in that subtree.

Formally, if you denote by \(S(u)\) the strength of the subtree rooted at node \(u\), then \[ S(u) = A[u] + \sum_{v \in \text{subtree}(u)\setminus\{u\}} A[v], \] where the subtree of \(u\) includes \(u\) and all its descendants when the tree is rooted at node 1.

Your task is to process each query and output the strength of the corresponding subtree.

inputFormat

The input is given via stdin and has the following format:

N
A[1] A[2] ... A[N]
u1 v1
u2 v2
... (N-1 lines representing edges)
Q
q1
q2
... qQ

Where:

• N is the number of nodes in the tree.
• A[i] represents the strength of node i.
• Each of the next N − 1 lines contains two integers u and v indicating that there is an edge between node u and node v.
• Q is the number of queries.
• Each of the next Q lines contains a single integer representing the query node.

outputFormat

Output a single line to stdout containing Q integers separated by a single space. The \(i^{th}\) integer should be the strength of the subtree rooted at the query node given in the \(i^{th}\) query.

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

15 6 8