Description

To improve her IQ, ZJY plans to travel to a new world. The cities in this world form a tree, and there is exactly one path between any two cities.

Each city has a type of gem with a certain price. To maximize profit, ZJY will choose to buy in city A and then resell in city B (only one purchase is allowed).

Because ZJY often acts cute when buying gems, the gem price in every city she passes through will increase. Let us calculate the maximum profit ZJY can earn after the trip. (For example, if the gem price in city A is $v$, then ZJY’s selling price is also $v$.)

Description

Input Format

• The first line contains a positive integer $n$, the number of cities.
• The next line contains $n$ positive integers, the initial prices $p$ of the gems in each city. Each initial price does not exceed $100$.
• Starting from the third line, there are $n-1$ lines. Each line contains two integers $x$ and $y$, indicating there is an edge between city $x$ and city $y$. City indices start from $1$.
• The next line contains a positive integer $q$, the number of queries.
• Each of the next $q$ lines contains three positive integers $a$, $b$, $v$, indicating that ZJY travels from $a$ to $b$, and the gem price in every city along the route (including both endpoints) increases by $v$.

Output Format

For each query, output the maximum possible profit ZJY can obtain. If the best result is a loss, output $0$.

3
1 2 3
1 2
2 3
2
1 2 100
1 3 100

1
1

5
1 2 3 4 5
1 2
1 3
2 4
4 5
6
1 5 50
2 4 500
3 4 5000
3 5 50000
1 3 500000
2 3 5000000

4
2
551
551
0
499499

Hint

Constraints

• For $30\%$ of the testdata, $n \le 100$, $q \le 10^4$.
• For $100\%$ of the testdata, $1 \le n, q \le 5 \times 10^4$, and at any time the gem price in any city does not exceed $10^9$.

Translated by ChatGPT 5