配点: 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 由于国家预算有限,您决定实施如下国家项目。
- N 群岛中的一岛 选择 s 并将该岛作为你的首都。
- 执行以下操作。
执行 N - 1 次。
- 在每次操作之前,选择一个可以从首都通过几座桥梁到达的岛屿。附近的岛屿,一个不存在的岛屿遥远的岛屿。 在桥梁一端在近岛、另一端在远岛的建设方案中,选择成本最低的方案实施。
- 操作 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 是不同的。
- 所有输入值都是整数。
小課題
- (5 点) N \leqq 2\,000,M \leqq 2\,000.
- (8 点) N \leqq 2\,000.
- (9 点) M = N - 1,A_j = j, B_j = j + 1 (1 \leqq j \leqq M),Q = 1.
- (18 点) M = N - 1,A_j = j, B_j = j + 1 (1 \leqq j \leqq M).
- (28 点) Q = 1.
- (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 号施工计划已执行。来自首都的新岛屿 3 变得可达。
- 3 号施工计划已执行。来自首都的新岛屿 2 变得可达。
- 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 满足约束。