AT_nikkei2019_2_final_g Road Trip

有一棵包含 $N$ 个顶点的无向树，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。第 $i$ 条边连接顶点 $A_i$ 和顶点 $B_i$，权值为 $C_i$。请注意，权值 $C_i$ 可能为负数。 我们将这棵树的连通子图称为“驾驶子树”，特别地，包含顶点 $u$ 和顶点 $v$ 的驾驶子树称为“$u-v$ 驾驶子树”。某个驾驶子树所包含的所有边的权值之和，称为该驾驶子树的“乐趣值”。 给定 $Q$ 个整数对 $(U_i, V_i)$，对于每个 $i$，请回答以下问题： - $U_i-V_i$ 驾驶子树的乐趣值可能取得的最大值是多少。

输入以如下格式从标准输入读入。 > $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$ 驾驶子树的乐趣值可能取得的最大值。

## 限制条件 - $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 - 对于第 $1$ 个询问，选择由顶点 $2, 3, 4$ 构成的子图作为驾驶子树时，乐趣值为 $20+(-1)$，这是 $2-3$ 驾驶子树乐趣值的最大值。 - 对于第 $2$ 个和第 $3$ 个询问，选择由顶点 $1, 2, 3, 5, 6, 7$ 构成的子图作为驾驶子树时，乐趣值为 $(-10)+20+1+3+2$，在这两个询问中这都是最大值。 由 ChatGPT 4.1 翻译