Subtree Sum at Specific Level in a Tree

You are given a tree with n vertices (numbered 1 through n) with each vertex assigned an integer value. The tree is rooted at vertex 1. You will be given Q queries. Each query consists of two integers, V and L. For each query, your task is to compute the sum of the values of the vertices in the subtree of V that are exactly L levels below V.

More formally, let level(x) denote the depth of vertex x (with level(1)=0). For a given query (V, L), you need to calculate:

[ S = \sum_{u \in \text{subtree}(V) ;\text{and}; level(u)=level(V)+L} \text{value}(u)]

It is guaranteed that the input forms a tree and that vertex 1 is the root.

inputFormat

The input is given via standard input and consists of several parts:

• The first line contains a single integer n (the number of vertices).
• The second line contains n space-separated integers representing the values of the vertices from vertex 1 to vertex n.
• The next n - 1 lines each contain two space-separated integers u and v, indicating that there is an edge between vertices u and v.
• The next line contains a single integer Q, the number of queries.
• The following Q lines each contain two space-separated integers V and L, representing a query as described above.

outputFormat

For each query, output a single integer on a new line—the sum of values of the vertices in the subtree of V that are exactly L levels below V.

## sample

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

90
90
20

</p>