[JOISC 2023 Day4] Security Guard

在 JOI 王国中，有 $N$ 座岛屿，编号从 $1$ 到 $N$。每座岛屿都有不安全程度 $S_i$。 在 JOI 王国中，使用船只作为交通工具连接各个岛屿。现有 $M$ 艘船只，编号从 $1$ 到 $M$，第 $j$ 艘船只连接着岛屿 $A_j$ 和 $B_j$。我们可以在需要时运行这些船只。乘坐几艘船只后，可从任意岛屿抵达其他所有岛屿。 今天，JOI 王国的首相 K 毅然决定引入新的船只，并要求所有船只必须遵守以下安全条件。 当一艘船只停泊在岛屿 $i\ (1\leq i \leq N)$ 时，其上的保安人数大于等于 $S_i$。 鉴于雇佣保对于每艘船只，将其停泊在与其相连的两座岛屿中的一座上，并在其上安置一定数量的保安人员。此外，还应满足以下条件：安十分昂贵，我们希望最小化雇佣的保安人数。只要满足“通过乘坐若干艘船只可从任意岛屿到达其他任意岛屿”这个条件，就可以废除目前正在运营的一些船只。 我们将按如下方法运营船只。这里，$k$ 是要引入的新的船只数。 + 对于这 $k$ 艘新的船只，选择它们相连接的两座岛屿。 + 我们选取一些（多于或等于 $0$ 艘，以下称为“废除船只”）船只予以废除。允许废除已经运行的新船只。 + 对于每艘船只，将其停泊在与其相连的两座岛屿中的一座上，并在其上安置一定数量的保安人员。此外，还应满足以下条件：对于所有岛屿对 $u, v\ (1\leq u\leq N,1\leq v\leq N)$，重复下面的操作若干次后可以将一位乘客从岛屿 $u$ 运送到岛屿 $v$。在整个过程中，必须使当一艘船只停泊在某座岛屿 $i$ 上时，其上的保安人数大于等于 $S_i$。 1. 在停泊在该岛屿上的船只上载客或保安。 2. 在抵达另一座岛屿之前，在停泊在目前所处的船只上卸客或保安。 3. 从目前所处的岛屿开往与之相连的另一座岛屿并停泊在那里。 由于预算有限，我们最多可以引入 $Q$ 艘新船。对于每个 $k\ (0\leq k\leq Q)$，首相 K 想要知道在引入 $k$ 艘新船的情况下，满足所有条件时最小可能雇用的保安人数。请编写一个程序，根据岛屿和船只路线的信息以及可以引入的新船数量，计算每个 $k$ 对应的最小人数。 Translate by @[ZeXic_B](https://www.luogu.com.cn/user/661274)

In JOI Kingdom, there are $N$ islands, numbered from $1$ to $N$. Each island has the insecurity level. The insecurity level of the island $i\ (1 \le i \le N)$ is $S_i$. In JOI Kingdom, ships between pairs of islands are mostly used as the methods of transportations. There are $M$ ships, numbered from $1$ to $M$. The ship $j\ (1 \le j \le M)$ connects the island $A_j$ and the island $B_j$. We can run ships when necessary. It is possible to travel from any island to any other island by taking a number of ships. In JOI Kingdom, there is a plan to introduce new ships. We can choose any pairs of islands where newly introduced ships connect. One day, an incident occurred. A ship at anchor was attacked. Prime minister K of JOI Kingdom decided to introduce new ships. He also demands that ships in JOI Kingdom should satisfy the following **Security Condition**. - When a ship is anchored at the island $i\ (1 \le i \le N)$, the number of security guards on the ship is greater than or equal to $S_i$. However, since it is expensive to hire security guards, we want to minimize the number of hired security guards. As long as the condition “it is possible to travel from any island to any other island by taking a number of ships” is satisfied, it is possible to abolish ships which are currently running. Therefore, we will run ships as follows. Here, $k$ is the number of newly introduced ships. 1. For each of the $k$ newly introduced ships, we choose two islands where it connects. 2. We choose a number of (more than or equal to $0$) ships, and we abolish them. It is allowed to abolish newly introduced ships. 3. For each of the ships, we anchor it at one of the two islands where it connects. We make a number of security guards get on it. Moreover, the following conditions should be satisfied. *Condition*     For every pair $u, v\ (1 \le u \le N, 1 \le v \le N)$ of islands, it is possible to transport a passenger from the island $u$ to the island $v$ by repeating the following operations a number of times. In the process, Security Condition should be satisfied all the time. - We make a passenger or security guards get on a ship which is anchored at the island where the passenger or security guards are staying. - We make a passenger or security guards get off a ship at the island where the ship is currently anchored. - We move a ship from the island where the ship is currently anchored to the other island where the ship connects. Since the budget is limited, we can introduce at most $Q$ new ships. For each $k\ (0 \le k \le Q)$, Prime minister K wants to know the minimum possible number of hired security guards if the number of newly introduced ships is $k$. Write a program which, given the information of islands and the routes of the ships and the number of new ships we can introduce, calculates the minimum possible number of hired security guards for each $k$.

Read the following data from the standard input. > $N\ M\ Q$ > > $S_1\ S_2\ \cdots\ S_N$ > > $A_1\ B_1$ > > $A_2\ B_2$ > > $\vdots$ > > $A_M\ B_M$

Write $Q+1$ lines to the standard output. The $(k+1)$-th line $(0 \le k \le Q)$ of output should contain the minimum possible number of hired security guards if the number of newly introduced ships is $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

#### 【样例解释 #1】 If the number of newly introduced ships is $0$, we need $7$ security guards. For example, the conditions are satisfied if we allocate the ships and $7$ security guards as follows. - The ship $1$ is initially anchored at the island $2$, and two security guards get on the ship $1$. - The ship $2$ is initially anchored at the island $2$, and two security guards get on the ship $2$. - The ship $3$ is initially anchored at the island $4$, and three security guards get on the ship $3$. Let us explain how to transport a passenger in the following two cases. - We transport a passenger from the island $1$ to the island $4$. - We transport a passenger from the island $3$ to the island $2$. We can transport a passenger from the island $1$ to the island $4$ as follows. The islands where the ships $1, 2, 3$ are anchored, and the numbers of security guards on the ships $1, 2, 3$ are written in this order. The numbers of security guards on the islands $1, 2, 3, 4$ are written in this order.  We can transport a passenger from the island $3$ to the island $2$ as follows.  Since it is impossible to satisfy the conditions if the number of security guards is less than or equal to $6$, output $7$. This sample input satisfies the constraints of Subtasks $2, 3, 4, 5, 6, 7$. #### 【样例解释 #2】 If the number of newly introduced ships is $0$, similarly as Sample Input $1$, we need $7$ security guards. If the number of newly introduced ships is $1$, we need $5$ security guards. For example, the conditions are satisfied if we allocate the ships and $5$ security guards as follows. - We introduce a new ship connecting the island $2$ and the island $4$. (In the following, we call it the ship $4$.) - We abolish the ship $3$. - We initially anchor the ship $1$ at the island $2$, and make two security guards get on the ship $1$. - We initially anchor the ship $2$ at the island $2$, and make one security guard get on the ship $2$. - We initially anchor the ship $4$ at the island $2$, and make two security guards get on the ship $4$. This sample input satisfies the constraints of Subtasks $5, 6, 7$. #### 【样例解释 #3】 If the number of newly introduced ships is $0$, we need $2$ security guards. For example, the conditions are satisfied if we allocate the ships and $2$ security guards as follows. - We abolish the ship $3$. - We initially anchor the ship $1$ at the island $1$, and make one security guard get on the ship $1$. - We initially anchor the ship $2$ at the island $1$, and make one security guard get on the ship $2$. This sample input satisfies the constraints of Subtasks $4, 5, 6, 7$. #### 【样例解释 #4】 This sample input satisfies the constraints of all the subtasks. #### 【样例解释 #5】 This sample input satisfies the constraints of Subtasks $3, 4, 5, 6, 7$. #### 【样例解释 #6】 This sample input satisfies the constraints of Subtasks $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 i \le N)$; - $1 \le A_j < B_j \le N\ (1 \le j \le M)$; - $(A_x, B_x) \neq (A_y, B_y)\ (1 \le x < y \le M)$; - It is possible to travel from any island to any other island by taking a number of ships; - Given values are all integers. | 子任务编号 | 分值 | 特殊限制 | | :----------: | :----------: | :----------: | | $1$ | $12$ | $M = N - 1$，$Q = 0$，$S_i \le 2\ (1 \le i \le N)$，$A_j = j$，$B_j = j + 1\ (1 \le j \le M)$ | | $2$ | $13$ | $M = N - 1$，$Q = 0$，$A_j = j$，$B_j = j + 1\ (1 \le j \le M)$ | | $3$ | $12$ | $M = N - 1$，$Q = 0$ | | $4$ | $13$ | $Q = 0$ | | $5$ | $8$ | $N \le 16$ | | $6$ | $18$ | $N \le 3 000$ | | $7$ | $24$ | 无 |