AT_nikkei2019_final_g Greatest Journey

有一棵包含 $N$ 个顶点的树，顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $N-1$。第 $i$ 条边连接顶点 $A_i$ 和 $B_i$。 现在有 $M$ 个人，每个人编号为 $1$ 到 $M$，他们将在这棵树上移动。第 $i$ 个人从顶点 $V_i$ 出发，恰好进行 $L_i$ 次如下操作： - 从当前所在顶点出发，自由选择一条连接该顶点的边，沿该边移动到相邻的顶点。若经过的边编号为 $x$，则获得 $C_x$ 分。 请对于每个 $i$，求出第 $i$ 个人在 $L_i$ 次操作中能够获得的总分的最大值。

输入按以下格式从标准输入读入。 > $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$ 次操作中能够获得的总分的最大值。

### 数据范围 - $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$ - 输入给出的图保证是一棵树。 - 所有输入均为整数。 ### 样例说明 1 第 $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$ 分。 由 ChatGPT 4.1 翻译