Path Sum Queries in a Tree

You are given a tree with N nodes. Each node has an integer value. The tree is rooted at node 1. You are required to answer Q queries. In each query, given two nodes u and v, compute the sum of the node values along the unique path from u to v.

The path sum for nodes u and v is defined as:

$$ S(u,v) = \sum_{x \in P(u,v)} value(x) $$

where \(P(u,v)\) is the set of nodes along the unique path between \(u\) and \(v)\.

inputFormat

The first line contains an integer T denoting the number of test cases. For each test case, the input is as follows:

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. N - 1 lines each containing two integers u and v indicating an undirected edge between nodes u and v.
4. An integer Q, the number of queries.
5. Q lines each containing two integers u and v representing a query.

outputFormat

For each query, output a single integer representing the sum of the node values along the unique path from u to v. Each answer should be printed on a new line.## sample

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

11
10
8