P15455 [JOI 2026 SemiFinal] 新的桥梁 / New Bridge

JOI 国由 $N$ 个岛屿组成，各岛屿编号为 $1$ 到 $N$。目前，该国没有连接岛屿之间的桥梁，居民生活十分不便。 因此，作为 JOI 国的大臣，你决定以国家事业的名义新建桥梁。现有 $M$ 个建桥计划，第 $j$ 个计划（$1 \le j \le M$）是用费用 $C_j$ 在岛屿 $A_j$ 和 $B_j$ 之间架设一座双向桥梁。这里，保证 $C_1, C_2, \dots, C_M$ 互不相同。另外，保证如果执行所有建设计划，所有岛屿将通过若干桥梁互相可达。 由于 JOI 国预算有限，你决定按以下方式实施国家事业： 1. 从 $N$ 个岛屿中选择一个岛屿 $s$，将其设为首都。 2. 进行以下操作 $N-1$ 次： - 在进行每次操作前，将已经通过若干桥梁从首都可达的岛屿称为**近岛**，其余岛屿称为**远岛**。从那些一端为近岛、另一端为远岛的建设计划中，选择费用最低的一个，并执行它。 3. 进行 $N-1$ 次操作后，国家事业结束。 这里，由建设计划满足的约束条件，可以证明以下事实： - 每次操作中，必定存在可供选择的建设计划。此外，被执行的建设计划是唯一确定的。 - 事业结束时，所有岛屿通过若干桥梁互相可达。 正在考虑移居 JOI 国的凛，为了决定住在哪个岛屿，决定按如下方式计算每个岛屿的“不便度”。岛屿 $i$（$1 \le i \le N$）的不便度定义如下： - 设以岛屿 $s$（$1 \le s \le N$）为首都实施国家事业时，岛屿 $i$ 从首都变为可达为止所执行的建设计划的数量为 $D_{s,i}$。这里，当 $s = i$ 时，$D_{s,i}$ 为 $0$。 - 岛屿 $i$ 的不便度是所有 $1 \le s \le N$ 的 $D_{s,i}$ 之和。 凛想要计算她考虑的 $Q$ 个候选迁居岛屿 $X_1, X_2, \dots, X_Q$ 的不便度。给定建设计划和候选迁居岛屿的信息，请编写程序求出这些岛屿的不便度。

输入从标准输入中以以下格式给出： $N\ M\ Q$ $A_1\ B_1\ C_1$ $A_2\ B_2\ C_2$ $\vdots$ $A_M\ B_M\ C_M$ $X_1$ $X_2$ $\vdots$ $X_Q$

输出 $Q$ 行。第 $k$ 行输出岛屿 $X_k$（$1 \le k \le Q$）的不便度。

#### 样例解释 1 例如，考虑以岛屿 $1$ 为首都实施国家事业的情况。此时，将按如下顺序执行建设计划： 1. 执行第 $1$ 个建设计划。从首都新可达岛屿 $3$。 2. 执行第 $3$ 个建设计划。从首都新可达岛屿 $2$。 3. 执行第 $5$ 个建设计划。从首都新可达岛屿 $4$。 由此，$D_{1,1} = 0,\ D_{1,2} = 2,\ D_{1,3} = 1,\ D_{1,4} = 3$。 因为 $D_{2,1} = 2,\ D_{3,1} = 2,\ D_{4,1} = 3$，所以岛屿 $1$ 的不便度为 $D_{1,1} + D_{2,1} + D_{3,1} + D_{4,1} = 0 + 2 + 2 + 3 = 7$。 另外，由于 $D_{2,3} = 1,\ D_{3,3} = 0,\ D_{4,3} = 1$，岛屿 $3$ 的不便度为 $D_{1,3} + D_{2,3} + D_{3,3} + D_{4,3} = 1 + 1 + 0 + 1 = 3$。 该输入样例满足子任务 $1,2,6$ 的数据范围。 ### 数据范围 - $2 \le N \le 300\,000$ - $1 \le M \le 600\,000$ - $1 \le Q \le N$ - $1 \le A_j < B_j \le N$（$1 \le j \le M$） - 当执行所有建设计划时，所有岛屿通过若干桥梁互相可达 - $1 \le C_j \le 10^9$（$1 \le j \le M$） - $C_1, C_2, \dots, C_M$ 互不相同 - $1 \le X_k \le N$（$1 \le k \le Q$） - $X_1, X_2, \dots, X_Q$ 互不相同 - 输入的所有值均为整数 ### 子任务 1. (5 分) $N \le 2000,\ M \le 2000$ 2. (8 分) $N \le 2000$ 3. (9 分) $M = N - 1$，且 $A_j = j,\ B_j = j + 1$（$1 \le j \le M$），$Q = 1$ 4. (18 分) $M = N - 1$，且 $A_j = j,\ B_j = j + 1$（$1 \le j \le M$） 5. (28 分) $Q = 1$ 6. (32 分) 无额外限制 翻译由 DeepSeek 完成