← 返回题目列表

AtCoder · nikkei2019_2_final_g

G. 公路旅行

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

配点: 1000 点

問題文

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)
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
A_1 B_1 C_1
:
A_{N-1} B_{N-1} C_{N-1}
Q
U_1 V_1
:
U_Q V_Q

出力

Q 行。 列出i 行中,U_i-V_i 请输出驾驶子树的乐趣的最大可能值。


入力例 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