配点: 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