G - Greatest Journey

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 1200

問題文

N 頂点の木があり、頂点には 1 から N までの番号が、辺には 1 から N-1 までの番号がついています。 辺 i は頂点 A_iB_i を結ぶ辺です。

1 から M までの番号のついた M 人の人が、今からこの木の上を移動します。 人 i は、頂点 V_i から出発し、以下の操作をちょうど L_i 回行います。

  • 今いる頂点に繋がっている辺を自由に一つ選び、その辺を通って隣の頂点へ移動する。 このとき、通った辺の番号が x なら、C_x 点を得る。

すべての i について、人 iL_i 回の操作で得られる得点の総和の最大値を求めてください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq A_i < B_i \leq N
  • 1 \leq C_i \leq 10^9
  • 1 \leq M \leq 10^5
  • 1 \leq V_i \leq N
  • 1 \leq L_i \leq 10^9
  • 入力で与えられるグラフは木である。
  • 入力される値はすべて整数である。

入力

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

N
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_{N-1} B_{N-1} C_{N-1}
M
V_1 L_1
V_2 L_2
\vdots
V_M L_M

出力

M 行出力せよ。 i 行目には、人 iL_i 回の操作で得られる得点の総和の最大値を出力せよ。


入力例 1

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

出力例 1

10
5
19

1 は、次のように行動すると 3 回の操作で得られる得点の総和を最大化できます。

  • 4 を使って移動し、頂点 5 から頂点 3 に移動する。2 点を得る。
  • 3 を使って移動し、頂点 3 から頂点 4 に移動する。4 点を得る。
  • 3 を使って移動し、頂点 4 から頂点 3 に移動する。4 点を得る。

2 は、次のように行動すると 1 回の操作で得られる得点の総和を最大化できます。

  • 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。

3 は、次のように行動すると 5 回の操作で得られる得点の総和を最大化できます。

  • 4 を使って移動し、頂点 5 から頂点 3 に移動する。2 点を得る。
  • 2 を使って移動し、頂点 3 から頂点 2 に移動する。2 点を得る。
  • 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。
  • 1 を使って移動し、頂点 1 から頂点 2 に移動する。5 点を得る。
  • 1 を使って移動し、頂点 2 から頂点 1 に移動する。5 点を得る。

入力例 2

12
9 10 13
5 8 78
1 7 96
3 5 56
7 9 99
4 12 36
7 12 45
7 11 37
8 9 69
2 7 60
6 7 71
10
9 7
8 1
1 2
11 18
1 18
3 5
9 17
9 13
9 16
5 5

出力例 2

693
78
195
1720
1779
401
1683
1287
1584
444