P13516 [KOI 2025 #1] 快递运输

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

2050 年，快递最优化研究所 (KOI, Kurier Optimization Institute) 建立了一个全国范围的基于机器人的快递运输网络。 该网络由 $N$ 个物流中心和连接它们的 $N-1$ 条道路组成，物流中心的编号从 1 到 $N$。每条道路的编号从 1 到 $N-1$，其中第 $i$ 条 ($1 \le i \le N-1$) 道路连接着 $U_i$ 和 $V_i$ 两个物流中心，道路的长度为 $W_i$。任何一个物流中心都可以通过一条或多条道路到达其他任何一个物流中心。也就是说，快递运输网络是一个由道路连接而成的连通结构。此外，任意两条不同的道路除了在它们的端点（即物流中心）外，不会在任何其他点相交。 我们将所有物流中心和所有道路上的任意点统称为一个**地点**。两个地点 $x, y$ 之间的距离 $d(x, y)$ 定义为从地点 $x$ 到达地点 $y$ 必须经过的最短路径长度。当然，若 $x=y$，则 $d(x, y) = 0$。 一些机器人被放置在特定的物流中心。每个机器人都带有一个给定的**通信范围**。一个通信范围为 $X$、初始位于地点 $p$ 的机器人，可以在满足 $d(p, z) \le X$ 的所有地点 $z$ 之间自由地、往复地移动，并可以在自己可移动范围内的任意地点取件或放件。 您作为研究所的研究员，需要判断是否可以利用协作的机器人，将快递从 1 号物流中心运输到 $N$ 号物流中心。也就是说，一个机器人可以将快递放在某个地点，然后另一个机器人可以从同一地点取走快递并继续运输。 您需要对总共 $Q$ 个场景进行分析，这些场景是相互关联的。第 $j$ ($1 \le j \le Q$) 个场景的形态如下： * 1 $A_j$ $B_j$：在第 $j-1$ 个场景的基础上，增加一个新机器人。该机器人的初始位置为 $A_j$ 号物流中心，通信范围为 $B_j$。 * 2 $C_j$：在第 $j-1$ 个场景的基础上，移除在第 $C_j$ 个场景中添加的机器人。保证在第 $C_j$ 个场景中确实添加了一个新的机器人，且同一个机器人不会被移除两次以上。 规定，第 0 个场景为初始状态，即没有任何机器人被放置。 对于每个场景，请编写一个程序来判断，机器人是否能够协作将快递从 1 号物流中心运输到 $N$ 号物流中心。

第一行给出两个整数 $N, Q$，以空格分隔。 接下来的 $N-1$ 行给出道路的信息。其中第 $i$ ($1 \le i \le N-1$) 行包含三个整数 $U_i, V_i, W_i$，以空格分隔。 接下来的 $Q$ 行给出场景的信息。其中第 $j$ ($1 \le j \le Q$) 行是关于第 $j$ 个场景的信息，格式如题面所述。

输出 $Q$ 行。第 $j$ ($1 \le j \le Q$) 行输出在第 $j$ 个场景下，如果快递能够被运输，则输出 **YES**，否则输出 **NO**。

### 样例 1 说明 假设我们考虑第八个场景。此时总共放置了六个机器人。其中一种可能的运输方式如下： 1. 位于 1 号物流中心的唯一一个机器人通信范围为 4。该机器人从 1 号物流中心拿起快递，并将其放在 3 号物流中心。 2. 位于 2 号物流中心的唯一一个机器人通信范围为 12。该机器人从 3 号物流中心移动并拿起快递，然后将其放在从 3 号物流中心到 4 号物流中心的道路上，距离 3 号物流中心为 1 的位置。 3. 位于 8 号物流中心的唯一一个机器人通信范围为 8。该机器人从 3 号到 4 号道路上距离 3 号物流中心为 1 的位置移动并拿起快递，然后将其放在从 4 号到 5 号道路上距离 4 号物流中心为 3 的位置。 4. 位于 10 号物流中心的唯一一个机器人通信范围为 9。该机器人从 4 号到 5 号道路上距离 4 号物流中心为 3 的位置移动并拿起快递，然后将其放在 11 号物流中心。 因为可以运输快递，所以应当输出 **YES**。 假设我们考虑第十个场景。此时总共放置了六个机器人。没有任何机器人能够拿起最初放在 1 号物流中心的快递。因此，无法运输快递。所以应当输出 **NO**。 ### 限制条件 * 给定的所有数都是整数。 * $2 \le N \le 200,000$ * $1 \le Q \le 200,000$ * 对于每个 $1 \le i \le N-1$ 的 $i$，有 $1 \le U_i, V_i \le N$ 且 $1 \le W_i \le 10^9$。 * 运输网络是连通的。 * 对于每个 $1 \le j \le Q$ 的 $j$： * 如果第 $j$ 个场景是增加新机器人，则 $1 \le A_j \le N$ 且 $1 \le B_j \le 10^{15}$。 * 如果第 $j$ 个场景是移除机器人，则 $1 \le C_j \le j-1$ 且第 $C_j$ 个场景必须是增加新机器人的场景。同一个机器人不会被移除超过一次。 ### 子任务 1. (8 分) $N \le 100, Q \le 6$。对于每个 $1 \le i \le N-1$ 的 $i$，$W_i \le 10$。 2. (13 分) 对于每个 $1 \le i \le N-1$ 的 $i$，$U_i = i, V_i = i+1$。此外，$N, Q \le 2500$。 3. (25 分) $N, Q \le 2500$。 4. (27 分) 对于每个 $1 \le i \le N-1$ 的 $i$，$U_i = i, V_i = i+1$。 5. (30 分) 所有的场景都是增加新机器人的场景。 6. (26 分) 对于每个 $1 \le i \le N-1$ 的 $i$，$W_i = 1$。对于所有 $j$，如果是增加新机器人的场景，$B_j \le 10$。 7. (21 分) 无附加限制条件。