← 返回题目列表

AtCoder · nikkei2019_final_g

G. 最伟大的旅程

中文机器翻译题面 查看原题

配点 : 1200 点

問題文

N 有一个顶点的树,顶点上有 1 减去 N 的数字位于两侧。 它们的编号最大为 1 减去 N-1 。 侧面 i 是顶点 是 A_i 和 按字典顺序比较 B_i 的边。 编号至

1 减去 M 编号最多为 M 人们现在将在这棵树上移动。 人 i 是顶点 V_i 开始,只需执行以下操作: 执行 L_i 次。 指定

  • 自由选择连接到当前顶点的一条边,并通过该边移动到下一个顶点。 此时经过的边数为 x 然后C_x 获得积分。

全部 i 关于人 求 i 是 在 L_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 行上应有人 i 是 在 L_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