問題文

N 頂点の無向木があり、頂点には 1 から N の、辺には 1 から N-1 の番号がついています。辺 i は 頂点 A_i と 頂点 B_i を結んでおり、C_i の重みを持ちます。重みの値は負である可能性もあることに注意してください。

この木の連結な部分グラフを「運転部分木」と呼び、特に頂点 u と頂点 v を含むものを「u-v 運転部分木」とします。ある運転部分木が持つ辺の重みの合計を、その運転部分木の「楽しさ」とします。

Q 個の整数組 (U_i, V_i) が与えられるので、各 i に対して次の質問に答えてください。

• U_i-V_i 運転部分木の楽しさとしてあり得る最大値は何か。

制約

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i < B_i \leq N\ (1 \leq i \leq N - 1)
• 与えられるグラフは木を成す
• -10^9 \leq C_i \leq 10^9\ (1 \leq i \leq N - 1)
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq U_i < V_i \leq N\ (1 \leq i \leq Q)
• 入力はすべて整数である

入力例 1

7
1 3 -10
2 3 20
3 4 -1
1 6 1
5 6 3
6 7 2
3
3 4
5 7
2 6

出力例 1

19
16
16

• 1 つ目の質問に対しては、頂点 2, 3, 4 からなる部分グラフを運転部分木として選ぶと楽しさは 20+(-1) となり、これが 2-3 運転部分木の楽しさのうち最大です。
• 2 つ目と 3 つ目の質問に対しては、頂点 1, 2, 3, 5, 6, 7 からなる部分グラフを運転部分木として選ぶと楽しさは (-10)+20+1+3+2 となり、どちらの質問でもこれが最大です。

入力例 2

7
1 3 -1100000
2 3 -1010000
3 4 -1001000
1 6 -1000100
5 6 -1000010
6 7 -1000001
3
3 4
5 7
2 6

出力例 2

-1001000
-2000011
-3110100

入力例 3

18
2 8 -133775141
3 16 -311103251
4 11 849496136
9 14 -442278959
8 13 946094213
8 14 714669159
5 8 210787603
5 11 8973730
10 15 581490293
10 16 -347827761
10 11 -126622449
7 11 431568122
6 7 -458490133
6 17 -314331217
1 6 -220056853
1 12 -981864951
12 18 183014767
20
1 15
7 10
6 12
1 18
3 16
4 8
9 12
2 14
1 11
3 8
14 17
4 17
12 18
3 17
1 10
5 9
9 15
4 13
5 11
4 7

出力例 3

2937909821
3616456807
2139059637
2139059637
2957525795
3616456807
1696780678
3482681666
2937909821
2957525795
2843635457
2843635457
2139059637
2184704445
2937909821
3174177848
3174177848
3616456807
3616456807
3616456807