AT_joi2026_semifinal_e 新たな橋 (New Bridge)

JOI 国是由 $N$ 个岛屿组成的国家，每个岛屿编号从 $1$ 到 $N$。目前，这个国家没有连接岛屿之间的桥梁，居民的生活很不方便。 因此，作为 JOI 国的大臣，你决定作为国家工程新建若干桥梁。有 $M$ 个桥梁建设计划，第 $j$ 个（$1 \leq j \leq M$）建设计划将以花费 $C_j$ 的代价，在岛屿 $A_j$ 和岛屿 $B_j$ 之间修建一座双向桥梁。保证 $C_1, C_2, \ldots, C_M$ 是互不相同的。另外，保证如果所有建设计划都被实施，那么所有岛屿通过若干桥梁一定可以互相到达。 由于 JOI 国的预算有限，你决定按如下方式实施国家工程： 1. 从 $N$ 个岛屿中选择一个岛屿 $s$，将其作为首都。 2. 重复以下操作 $N-1$ 次： - 在每次操作前，将能通过已建的桥从首都到达的岛屿称为**近岛**，其他岛屿为**远岛**。在包含一个近岛和一个远岛两端的所有建设计划中，选择花费最小的那一个并执行这个建设计划。 3. 执行 $N-1$ 次操作后，国家工程结束。 根据建设计划的限制，可以证明以下事实： - 每次操作时，一定存在可以选择的建设计划，且所选的建设计划是唯一的。 - 当工程结束时，所有岛屿能通过已建的桥梁互相到达。 凛想要搬到 JOI 国，打算以某个岛屿作为居所。她想要计算每个岛屿的**不便度**。对于岛屿 $i$（$1 \leq i \leq N$），其不便度定义如下： - 当以岛屿 $s$（$1 \leq s \leq N$）为首都进行国家工程时，岛屿 $i$ 从首都出发能够到达为止所需要执行的建设计划数记作 $D_{s,i}$。当 $s=i$ 时，$D_{s,i}=0$。 - 岛屿 $i$ 的不便度为对所有 $1 \leq s \leq N$ 的 $D_{s,i}$ 的总和。 凛想要知道她考虑搬去的 $Q$ 个岛屿 $X_1, X_2, \ldots, 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 \leq k \leq Q$）的不便度。

## 小子任务 1. （$5$ 分）$N \leq 2\,000$，$M \leq 2\,000$。 2. （$8$ 分）$N \leq 2\,000$。 3. （$9$ 分）$M = N - 1$，$A_j = j, B_j = j + 1$（$1 \leq j \leq M$），$Q = 1$。 4. （$18$ 分）$M = N - 1$，$A_j = j, B_j = j + 1$（$1 \leq j \leq M$）。 5. （$28$ 分）$Q = 1$。 6. （$32$ 分）无其他限制。 --- ## 样例解释 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 该输入样例满足小子任务 $1, 2, 4, 6$ 的限制。 --- ## 样例解释 3 该输入样例满足小子任务 $1, 2, 5, 6$ 的限制。 # 数据范围 - $2 \leq N \leq 300\,000$。 - $1 \leq M \leq 600\,000$。 - $1 \leq Q \leq N$。 - $1 \leq A_j < B_j \leq N$（$1 \leq j \leq M$）。 - 如果所有建设计划都实施，所有岛屿可以通过若干桥梁互相到达。 - $1 \leq C_j \leq 10^9$（$1 \leq j \leq M$）。 - $C_1, C_2, \ldots, C_M$ 互不相同。 - $1 \leq X_k \leq N$（$1 \leq k \leq Q$）。 - $X_1, X_2, \ldots, X_Q$ 互不相同。 - 所有输入数据均为整数。 由 ChatGPT 5 翻译