October 4, 2017

# 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

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!

One Comment

only the last test case didnot passed? how to solve it?