403362: GYM101138 J Valentina and the Gift Tree

The Valentina's birthday is coming soon! Her parents love her so much that they are preparing some gifts to give her. Valentina is cute and smart and her parents are planning to set an interesting task for her.

They prepared a tree (a connected graph without cycles) with one gift in each vertex. Vertices are numbered 1 through n and the i-th of them contains a gift with value g_i (a value describing Valentina's happiness if she gets a gift from this vertex). All gifts are wrapped so Valentina doesn't know their values.

Note that g_i may be negative and it would mean that Valentina doesn't like the gift (do you remember when your parents gave you clothes or toys not adequate to your interests?).

Let's consider the following process:

1. Valentina chooses two vertices a and b (not necessarily distinct).
2. She unpacks all gifts on the path connecting a and b and thus she sees their values.
3. She chooses some part of the path connecting a and b. The chosen part must be connected and can't be empty (hence, it must be a path).
4. Valentina takes all gifts in the chosen part of the path and her total happiness is equal to the sum of the values of taken gifts.

Valentina is smart and for chosen a and b she will choose a part resulting in the biggest total happiness.

In order to maximize her chance to get a good bunch of gifts, parents allow her to ask q questions, each with two numbers a and b. For each Valentina's question parents will tell her the answer, i.e. the maximum total happiness for chosen a and b.

They noticed that answering Valentina's questions is an interesting problem. They want to know if you are smart enough to correctly answer all questions.

The first line of the input contains one integer n (2 ≤ n ≤ 10⁵) — the size of the tree.

Each of the next n - 1 lines contains two integers u_i and v_i (1 ≤ u_i, v_i ≤ n) — indices of two vertices connected with an edge. The given edges are guaranteed to describe a tree.

The next line contains n integers g₁, g₂, ... g_n ( - 10⁹ ≤ g_i ≤ 10⁹).

Then, the questions are given. One line contains an integer q (1 ≤ q ≤ 500 000) — the number of questions.

Finally, each of the last q lines contains two integers a_i and b_i (1 ≤ a_i, b_i ≤ n), describing one question.

For each of the q questions find the maximum happiness of Valentina if she has to choose a non-empty part of the given path. For every question print the answer in a separate line.

6
1 2
1 3
1 4
4 5
4 6
-1 2 2 -2 5 8
6
2 5
2 3
1 5
5 3
1 4
5 6

5
3
5
5
-1
11