AT_pakencamp_2025_day2_d Ice Melting

在パケン王国的パケン雪原有一个洞窟，洞窟内有 $N$ 个房间。每个房间 $i$ 初始时有大小为 $A_i$ 的冰。此外，洞窟内有 $N-1$ 条双向连接房间的通道，第 $i$ 条通道连接房间 $u_i$ 和房间 $v_i$，仅当 $c_i=1$ 时，在该通道上放置有热源。这里保证对于任意房间，可以通过若干通道到达任意其他房间。 从时刻 $0$ 起，房间 $i$ 中的冰仅在满足下列条件时，以每单位时间 $1$ 的速度减小。冰的大小不会小于 $0$。 - 房间 $i$ 可以在不经过含有冰的其它房间的情况下，抵达某一个有热源的通道。 给出 $Q$ 个询问。第 $i$ 个询问如下： - 考虑从房间 $a_i$ 走到房间 $b_i$，选择经过通道数最少的路径（可以证明，路径是唯一的）。在这条路径上所经过的所有房间（包括 $a_i, b_i$ 所在房间）中，在时刻 $t_i$ 时的冰的大小之和是多少。

输入以如下格式给出。 > $N$ > $A_1\ A_2\ \dots\ A_N$ > $u_1\ v_1\ c_1$ > $u_2\ v_2\ c_2$ > $\vdots$ > $u_{N-1}\ v_{N-1}\ c_{N-1}$ > $Q$ > $a_1\ b_1\ t_1$ > $a_2\ b_2\ t_2$ > $\vdots$ > $a_Q\ b_Q\ t_Q$

输出共 $Q$ 行，第 $i$ 行输出第 $i$ 个询问的答案，输出为整数。

## 子任务 1. （$7$ 分）$N, Q \leq 1000, u_i = i, v_i = i+1\ (1 \le i \le N-1)$。 2. （$8$ 分）$N, Q \leq 1000$。 3. （$7$ 分）$u_i = i, v_i = i+1\ (1 \le i \le N-1)$，且任意 $1 \le i, j \le Q$，均有 $t_i = t_j$。 4. （$14$ 分）$u_i = i, v_i = i+1\ (1 \le i \le N-1)$，且对所有 $1 \le i \le Q$，$(a_i, b_i) = (1, N)$。 5. （$28$ 分）$u_i = i, v_i = i+1\ (1 \le i \le N-1)$。 6. （$6$ 分）$N, Q \leq 100000$，且任意 $1 \le i, j \le Q$，均有 $t_i = t_j$。 7. （$15$ 分）$N, Q \leq 100000$。 8. （$15$ 分）无额外约束。 ## 样例解释 1 时刻 $0$，房间 $1$ 和房间 $2$ 能（不经过其他有冰的房间）抵达有热源的通道，因此冰开始融化。房间 $3$ 因为房间 $2$ 的冰阻挡，无法到达热源，暂时不会融化。 - 第 $1$ 个询问询问的是时刻 $5$ 的状态：房间 $1$ 冰的大小为 $10 - 5 = 5$，房间 $2$ 的冰为 $20 - 5 = 15$；房间 $3$ 的冰还未开始融化，还是 $30$。路径上所经过的房间为 $1, 2, 3$，所以答案是 $5 + 15 + 30 = 50$。 - 第 $2$ 个询问询问的是时刻 $10$ 的状态：房间 $1$ 冰已完全融化（为 $0$），房间 $2$ 的冰为 $20 - 10 = 10$。路径上所经过的房间为 $2, 3$，所以答案是 $10 + 30 = 40$。 ## 数据范围 - $2 \le N \le 200000$ - $1 \le Q \le 200000$ - $1 \le A_i \le 10^9$ - $1 \le u_i, v_i \le N$ - $u_i \neq v_i$ - $c_i \in \{0, 1\}$ - 至少存在一个 $i$ 使得 $c_i=1$ - $1 \le a_i, b_i \le N$ - $0 \le t_i \le 10^{10}$ - 保证任意一个房间均可到达所有其它房间 - 所有输入数据均为整数 由 ChatGPT 5 翻译