题目描述

题目译自 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

如果新引进的船是 $0$，需要 $7$ 个警卫。按如下方式安排船和警卫就可以满足条件了：

• 船 $1$ 最初停在岛屿 $2$，有 $2$ 名警卫登上船 $1$
• 船 $2$ 最初停在岛屿 $2$，有 $2$ 名警卫登上船 $2$
• 船 $3$ 最初停在岛屿 $4$，有 $3$ 名警卫登上船 $3$

下面用如下两个例子解释如何运输乘客：

• 把乘客从岛屿 $1$ 运输到岛屿 $4$
• 把乘客从岛屿 $3$ 运输到岛屿 $2$

可以按如下方法把乘客从岛屿 $1$ 运输到岛屿 $4$。船停靠的岛屿和船上的警卫数均按船 $1,2,3$ 的顺序展示。岛屿上的警卫数按岛屿 $1,2,3,4$ 的顺序展示。

#	操作	船停靠的岛屿	船上警卫数	岛上警卫数
-	-	$2,2,4$	$2,2,3$	$0,0,0,0$
$1$	让船 $1$ 从岛屿 $2$ 移动到岛屿 $1$	$1,2,4$
$2$	让一个乘客上船 $1$
$3$	让船 $1$ 从岛屿 $1$ 移动到岛屿 $2$	$2,2,4$
$4$	让一个乘客和一个警卫下船 $1$		$1,2,3$	$0,0,1,0$
$5$	让一个乘客和一个警卫上船 $2$		$1,3,3$	$0,0,0,0$
$6$	让船 $2$ 从岛屿 $2$ 移动到岛屿 $3$	$2,3,4$
$7$	让一个乘客下船 $2$
$8$	让船 $3$ 从岛屿 $4$ 移动到岛屿 $3$	$2,3,3$
$9$	让一个乘客上船 $3$
$10$	让船 $3$ 从岛屿 $3$ 移动到岛屿 $4$	$2,3,4$
$11$	让一个乘客下船 $3$

可以按如下方法把乘客从岛屿 $3$ 运输到岛屿 $2$。

#	操作	船停靠的岛屿	船上警卫数量	岛上警卫数
-	-	$2,2,4$	$2,2,3$	$0,0,0,0$
$1$	让一个警卫下船 $1$		$1,2,3$	$0,1,0,0$
$2$	让一个警卫上船 $2$		$1,3,3$	$0,0,0,0$
$3$	让船 $2$ 从岛屿 $2$ 移动到岛屿 $3$	$2,3,4$
$4$	让一个乘客上船 $2$
$5$	让船 $2$ 从岛屿 $3$ 移动到岛屿 $2$	$2,2,4$
$6$	让一个乘客下船 $2$

因为不可能雇佣小于等于 $6$ 名警卫以满足条件，所以输出 $7$。

这组样例满足子任务 $2,3,4,5,6,7$ 的限制。

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

7
5

如果新引进的船数量为 $0$，类似样例 1 的，需要 $7$ 名警卫。

如果新引进的船数量为 $1$，需要 $5$ 名警卫。可以按如下方式分配警卫以满足条件：

• 用引进的船连接岛屿 $2$ 和岛屿 $4$（下面称这条船为船 $4$）
• 停止船 $3$ 所在航线
• 船 $1$ 最初停在岛屿 $2$，有 $2$ 名警卫登上船 $1$
• 船 $2$ 最初停在岛屿 $2$，有 $1$ 名警卫登上船 $2$
• 船 $4$ 最初停在岛屿 $2$，有 $2$ 名警卫登上船 $4$

这组样例满足子任务 $5,6,7$ 的限制。

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

2

如果新引进的船数量为 $0$，需要 $2$ 名警卫。可以按如下方式分配警卫以满足条件：

• 停止船 $3$ 所在航线
• 船 $1$ 最初停在岛屿 $1$，有 $1$ 名警卫登上船 $1$
• 船 $2$ 最初停在岛屿 $1$，有 $1$ 名警卫登上船 $2$

这组样例满足子任务 $4,5,6,7$ 的限制。

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

这组样例满足子任务 $3,4,5,6,7$ 的限制。

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

这组样例满足子任务 $5,6,7$ 的限制。

数据范围与提示

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

• $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$