← 返回题目列表

AtCoder · joi2026_semifinal_e

E. 新桥

中文机器翻译题面 查看原题

配点: 100 点

問題文

JOI国家是 N 它是一个由岛屿组成的国家,每个岛屿都有 1 从 N 。目前,该国没有连接岛屿的桥梁,居民生活不便。

因此,您,JOI国家的部长,决定将建造一座新桥作为国家项目。建造一座桥梁的施工计划 M 可用,j 番目 (1 \leqq j \leqq 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 \leqq i \leqq N)的不便程度定义如下。 实施以

  • 島 s (1 \leqq s \leqq N)为资金的国家项目时, i 是从首都到达之前已实施的建设项目数量。 D_{s, i} 。在这里, 当s = i 什么时候 D_{s, i} 为 0 设定为。
  • 島 i 的不便之处在于 对于 1 \leqq s \leqq N 让它成为 D_{s, i} 的总和。

Rin 正在考虑将其作为一个可能搬到的地方。 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 \leqq k \leqq Q)的不便程度。


制約

  • 2 \leqq N \leqq 300\,000.
  • 1 \leqq M \leqq 600\,000.
  • 1 \leqq Q \leqq N.
  • 1 \leqq A_j < B_j \leqq N (1 \leqq j \leqq M).
  • 如果所有建设计划都得到执行,所有岛屿将能够通过桥梁相互到达。
  • 1 \leqq C_j \leqq 10^9 (1 \leqq j \leqq M).
  • C_1, C_2,\ldots,C_M 是不同的。
  • 1 \leqq X_k\leqq N (1 \leqq k \leqq Q).
  • X_1, X_2, \ldots, X_Q 是不同的。
  • 所有输入值都是整数。

小課題

  1. (5 点) N \leqq 2\,000,M \leqq 2\,000.
  2. (8 点) N \leqq 2\,000.
  3. (9 点) M = N - 1,A_j = j, B_j = j + 1 (1 \leqq j \leqq M),Q = 1.
  4. (18 点) M = N - 1,A_j = j, B_j = j + 1 (1 \leqq j \leqq M).
  5. (28 点) Q = 1.
  6. (32 点)没有额外的限制。

入力例 1

4 5 2
1 3 2
1 4 4
2 3 1
2 4 5
3 4 3
1
3

出力例 1

7
3

例如,一个岛屿 考虑以 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

5 4 5
1 2 3
2 3 1
3 4 4
4 5 2
1
2
3
4
5

出力例 2

12
8
7
10
13

此输入示例是一个小作业。 1, 2, 4, 6 满足约束。


入力例 3

10 20 1
1 2 808642746
1 3 990324141
1 4 69919024
1 5 794837863
3 6 84751636
1 7 491226767
3 8 314795065
1 9 347506932
1 10 709806198
2 3 103026123
9 10 270175384
4 8 133038160
4 10 592110162
2 10 708615085
6 10 262209760
5 10 75049025
7 9 367273075
6 9 264231132
3 10 909786421
2 7 135810916
10

出力例 3

43

此输入示例是一个小作业。 1, 2, 5, 6 满足约束。