题目描述

题目译自 JOISC 2023 Day4 T2 「警備員 / Security Guard」

JOI 国有 $N$ 座岛屿，编号为 $1$ 到 $N$。每个岛屿有一个不安全等级，岛屿 $i\ (1\le i\le N)$ 的不安全等级为 $S_i$。

在 JOI 国，船运是通用的运输方式。有 $M$ 条船，编号为 $1$ 到 $M$。船 $j\ (1\le j\le M)$ 连接岛屿 $A_j$ 和 $B_j$。船可根据需要随时出航。可以通过一些数量的船从任意一个岛屿前往任意其他岛屿。

JOI 国计划引入新船。我们可以选择任意岛屿对，让这对岛屿用新引进的船直接通航。

一天发生了一个事故，一条停泊的船被袭击了。JOI 国的首相 K 决定引入新船的同时，还需要满足以下安全条件：

• 当一艘船停靠在岛屿 $i\ (1\le i\le N)$ 时，在船上的警卫数量要大于等于 $S_i$

然而，因为雇佣警卫很贵，我们想最小化雇佣警卫的人数。只要满足「可以通过一些数量的船从任意一个岛屿前往任意其他岛屿」这一条件，可以停止目前正在运行的航线。

因此，我们会按如下方法运营航线。此处，$k$ 是新引进的船只数：

1. 对于新引进的 $k$ 艘船中的每一艘，选择两座岛屿，让这对岛屿用新引进的船直接通航

2. 选择一些（大于等于 $0$ 艘）船并停止这条航线。允许停止新引进的船形成的航线

3. 对于每艘船，让它停靠在它所连接的两座岛屿中的一座。然后安排一定数量的警卫上船。此外，还需满足如下条件：

   条件：对于每对岛屿 $u,v\ (1\le u,v\le N)$，可以通过重复如下操作几次来运输一名乘客从岛屿 $u$ 前往岛屿 $v$。在这个过程中，应全程满足安全条件：

   • 让一个乘客或警卫登上停靠在这个乘客或警卫所在岛的船
   • 让一个乘客或警卫在这艘船停靠的岛下船
   • 让一艘船从它目前停靠的岛出发前往它所连接的另一个岛

因为预算有限，可以最多引入 $Q$ 艘船。对于每个 $k\ (0\le k\le Q)$，K 首相想知道如果新引进 $k$ 艘船的话最少要雇佣多少警卫。

给定岛屿，航线信息和可以引进的船数，写一个程序计算对于每个 $k$，当引入 $k$ 艘船时最少要雇佣的警卫人数。

输入格式

第一行三个整数 $N,M,Q$。

第二行 $N$ 个整数 $S_1,S_2,\ldots,S_N$。

接下来 $M$ 行，每行两个整数 $A_i,B_i$。

输出格式

输出 $Q+1$ 行，第 $(k+1)\ (0\le k\le Q)$ 行输出一个整数，表示当新引进 $k$ 艘船时，最少要雇佣的警卫人数。

4 3 0
2 1 3 2
1 2
2 3
3 4

7

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

7
5

3 3 0
1 1 1
1 2
1 3
2 3

2

8 7 0
2 2 2 2 2 2 2 2
1 2
2 3
3 4
4 5
5 6
6 7
7 8

14

8 7 0
16 39 36 23 15 48 23 56
1 2
1 3
2 4
2 5
3 6
3 7
7 8

245

10 13 4
314 159 265 358 979 323 846 264 338 327
1 2
1 4
2 3
2 5
3 6
4 5
4 7
5 6
5 8
6 9
7 8
8 9
9 10

3139
2901
2722
2567
2461

数据范围与提示

对于所有输入数据，满足：

• $2\le N\le 2\times 10^5$
• $N-1\le M\le 4\times 10^5$
• $0\le Q\le 2\times 10^5$
• $1\le S_i\le 10^9$
• $1\le A_j<B_j\le N,(A_x,B_x)\neq (A_y,B_y)\ (1\le x<y\le M)$
• 可以通过一些数量的船从任意一个岛屿前往任意其他岛屿

详细子任务附加限制及分值如下表所示。

子任务编号	附加限制	分值
$1$	$M=N-1,Q=0,S_i\le 2,A_j=j,B_j=j+1$	$12$
$2$	$M=N-1,Q=0,A_j=j,B_j=j+1$	$13$
$3$	$M=N-1,Q=0$	$12$
$4$	$Q=0$	$13$
$5$	$N\le 16$	$8$
$6$	$N\le 3\ 000$	$18$
$7$	无附加限制	$24$