Problem L: Tree Fragments

Problem

あいちゃんは、$N$個の頂点と$N-1$本の辺からなる木$T$を持っている。各頂点には$1$から$N$までの番号と、正の整数の重みがついている。

次の$Q$回のクエリに順に答えよ。

• $1 \le a_i,b_i \le N$($a_i \ne b_i$)が与えられるので、$T$の$a_i$-$b_i$パス上の頂点とそれに接続する辺を取り除いてできる、いくつかの連結成分の中で、重みが最大となる連結成分の重みを出力する。そのような連結成分が1つもない場合、0と出力する。

ただし、連結成分の重みはその連結成分に含まれる頂点の重みの和で定義される。

Input

入力は以下の形式で与えられる。

$N$
$w_1$ $w_2$ ... $w_N$
$u_1$ $v_1$
$u_2$ $v_2$
...
$u_{N-1}$ $v_{N-1}$
$Q$
$a_1$ $b_1$
$a_2$ $b_2$
...
$a_Q$ $b_Q$

入力はすべて整数で与えられる。

1行目に$T$の頂点数$N$が与えられる。
2行目に頂点$i$($1 \le i \le N$)の重み$w_i$が空白区切りで与えられる。
3行目以降の$N$-1行に辺$_i$($1 \le i \le N-1$)の端点$u_i,v_i$が空白区切りで与えられる。
$N$+2行目にクエリの数$Q$が与えられる。
$N$+3行目以降の$Q$行に、クエリ$_i$($1 \le i \le Q$)を表す$a_i,b_i$が空白区切りで与えられる。

Constraints

入力は以下の条件を満たす。

• $2 \le N \le 10^5$
• $1 \le Q \le 10^5$
• $1 \le w_i \le 10^8$($1 \le i \le N$)
• $1 \le u_i,v_i \le N$($1 \le i \le N-1$)
• $u_i \ne v_i$
• $i \ne j$なら$(u_i,v_i) \ne (u_j,v_j)$かつ$(u_i,v_i) \ne (v_j, u_j)$
• $1 \le a_i,b_i \le N$($1 \le i \le Q$)
• $a_i \ne b_i$

Ouput

クエリ毎に、0または重みが最大となる連結成分の重みを1行に出力する。

Sample Input 1

10
1 2 3 4 5 6 7 8 9 10
1 2
2 3
3 4
3 5
2 6
6 7
2 8
8 9
8 10
3
3 8
7 1
7 10

Sample Output 1

13
27
12

Sample Input 2

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

Sample Output 2

12
0
5

Sample Input 3

15
3 8 4 2 6 5 1 2 10 3 4 2 6 1 1
1 2
2 3
3 4
3 5
2 6
6 7
6 8
1 9
9 10
10 11
10 12
9 13
13 14
13 15
5
1 1
2 7
6 10
1 15
3 4

Sample Output 3

28
30
12
28
46

Note

Link

 

---