Tree Sum Query

2 secs 1024 MB
magurofly

問題文


個の頂点と 本の辺がある連結な無向グラフが与えられます。 番目の頂点には整数 が書かれています。 番目の辺は頂点 と頂点 を結んでいます。

個のクエリが与えられます。 番目のクエリでは頂点 と頂点 が指定されます。 を結ぶ最短経路上の頂点に書かれた数の総和を求めてください。

制約


  • 入力は全て整数

入力


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

出力


それぞれのクエリについて、答えを出力せよ。

入出力例1


入力例1
4
2 1 8 4
1 2
2 4
2 3
3
1 4
4 3
4 2
出力例1
7
13
5

入出力例2


入力例2
4
1 -2 -8 4
1 2
4 2
2 3
2
4 1
2 3
出力例2
3
-10

入出力例3


入力例3
4
1 10 100 1000
1 2
2 3
3 4
4
1 3
2 4
2 3
1 4
出力例3
111
1110
110
1111

Submit


Go (1.14)