Skipping Subpath Sum

           Skipping Subpath Sum

There is a tree  with  vertices numbered from  to . In addition,  is the value assigned to the -th vertex.

Consider any path  in the tree. We define a skipping sum of this path to be the maximum of the two below values:

 where  is the maximum odd integer not greater than .  where  is the maximum even integer not greater than .

In other words,  is the sum of values of every second vertex in  starting from its first vertex, while  is the sum of values of every second vertex of  starting from its second vertex. If  consist of only a single vertex, then  for such . The skipping sum of  is defined as .

Now, consider two vertices  of . In the tree, there is a unique path between them. Let  be that path. A subpath of  is any non-empty consecutive subsequence of vertices in . We define a skipping subpath sum of to be the maximum value of a skipping sum among all subpaths of .

The goal of this problem is to handle  queries. The -th query contains two vertices  and asks for the value of the skipping subpath of a path between  and .

Input Format

In the first line, there is a single integer  denoting the number of vertices in the tree. In the second line, there are space-separated values . After that,  lines follow. Each of them contains two space-separated integers  and  denoting that there is an edge between  and  in the tree. In the next line, there is a single integer  denoting the number of queries to handle. Then,  lines follow. In the -th of them, there are two space-separated integers  and , and asks for the value of the skipping subpath sum of a path between  and .

Constraints

 
 
 

Output Format

Print exactly  lines. In the -th of them, print the answer to the -th query.

Sample Input 0

5
3 -2 1 -1 2
0 1
1 2
0 3
3 4
5
2 4
1 3
3 3
4 1
4 0

Sample Output 0

6
3
0
5
5

Explanation 0

For the  query, , . Therefore, .

For the  query, , . Therefore, .

For the  query, , . Therefore, .

For the  query, , . Therefore, .

For the  query, , . Therefore, .

Code:

Coming soon!


Please do comment If u have any Queries!