2023-sp_Security_Guard — JOI JOI_spring
Task type: batch | Time limit: 3 s | Memory limit: 1024 MB | Difficulty: 24
Algorithms: data structures, greedy, graph theory, spanning tree

![](_page_0_Picture_0.jpeg)

The 22nd Japanese Olympiad in Informatics (JOI 2022/2023)
Spring Training/Qualifying Trial
March 18–22, 2023 (Komaba, Tokyo)

## Security Guard

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 ≤ *i* ≤ *N*) is *S<sub>i</sub>*.

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 ≤ *j* ≤ *M*) connects the island *A<sub>j</sub>* and the island *B<sub>j</sub>*. 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 ≤ *i* ≤ *N*), the number of security guards on the ship is greater than or equal to *S<sub>i</sub>*.

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 ≤ *u* ≤ *N*, 1 ≤ *v* ≤ *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, the 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.

![](_page_1_Picture_0.jpeg)

Since the budget is limited, we can introduce at most *Q* new ships. For each *k* (0 ≤ *k* ≤ *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*.

### Input

Read the following data from the standard input:

```
N M Q
S1 S2 ... SN
A1 B1
A2 B2
:
AM BM
```

### Output

Write *Q*+1 lines to the standard output. The (*k*+1)-th line (0 ≤ *k* ≤ *Q*) of output should contain the minimum possible number of hired security guards if the number of newly introduced ships is *k*.

### Constraints

*   2 ≤ *N* ≤ 200 000.
*   *N* − 1 ≤ *M* ≤ 400 000.
*   0 ≤ *Q* ≤ 200 000.
*   1 ≤ *S<sub>i</sub>* ≤ 10<sup>9</sup> (1 ≤ *i* ≤ *N*).
*   1 ≤ *A<sub>j</sub>* < *B<sub>j</sub>* ≤ *N* (1 ≤ *j* ≤ *M*).
*   (*A<sub>x</sub>*, *B<sub>x</sub>*) ≠ (*A<sub>y</sub>*, *B<sub>y</sub>*) (1 ≤ *x* < *y* ≤ *M*).
*   It is possible to travel from any island to any other island by taking a number of ships.
*   Given values are all integers.

![](_page_2_Picture_0.jpeg)

### Subtasks

1.  (12 points) *M* = *N* − 1, *Q* = 0, *S<sub>i</sub>* ≤ 2 (1 ≤ *i* ≤ *N*), *A<sub>j</sub>* = *j*, *B<sub>j</sub>* = *j* + 1 (1 ≤ *j* ≤ *M*).
2.  (13 points) *M* = *N* − 1, *Q* = 0, *A<sub>j</sub>* = *j*, *B<sub>j</sub>* = *j* + 1 (1 ≤ *j* ≤ *M*).
3.  (12 points) *M* = *N* − 1, *Q* = 0.
4.  (13 points) *Q* = 0.
5.  (8 points) *N* ≤ 16.
6.  (18 points) *N* ≤ 3 000.
7.  (24 points) No additional constraints.

### Sample Input and Output

| Sample Input 1 | Sample Output 1 |
| :------------- | :------------- |
| `4 3 0`        | `7`            |
| `2 1 3 2`      |                |
| `1 2`          |                |
| `2 3`          |                |
| `3 4`          |                |

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.

![](_page_3_Picture_0.jpeg)

| #  | Operation                                                    | The islands <br>where the <br>ships are <br>anchored | The numbers <br>of security <br>guards on <br>the ships | The numbers <br>of security <br>guards on <br>the islands |
| :--: | :----------------------------------------------------------- | :---------------------------------------------------------: | :------------------------------------------------------------: | :------------------------------------------------------------: |
| -  | -                                                            |                           2,2,4                           |                             2,2,3                              |                             0,0,0,0                              |
| 1  | Move the ship 1 from the island 2 to the island 1            |                           1,2,4                           |                             2,2,3                              |                             0,0,0,0                              |
| 2  | Make a passenger get on the ship 1                           |                           1,2,4                           |                             2,2,3                              |                             0,0,0,0                              |
| 3  | Move the ship 1 from the island 1 to the island 2            |                           2,2,4                           |                             2,2,3                              |                             0,0,0,0                              |
| 4  | Make one security guard and the passenger get off the ship 1 |                           2,2,4                           |                             1,2,3                              |                             0,1,0,0                              |
| 5  | Make one security guard and the passenger get on the ship 2  |                           2,2,4                           |                             1,3,3                              |                             0,0,0,0                              |
| 6  | Move the ship 2 from the island 2 to the island 3            |                           2,3,4                           |                             1,3,3                              |                             0,0,0,0                              |
| 7  | Make the passenger get off the ship 2                        |                           2,3,4                           |                             1,3,3                              |                             0,0,0,0                              |
| 8  | Move the ship 3 from the island 4 to the island 3            |                           2,3,3                           |                             1,3,3                              |                             0,0,0,0                              |
| 9  | Make the passenger get on the ship 3                         |                           2,3,3                           |                             1,3,3                              |                             0,0,0,0                              |
| 10 | Move the ship 3 from the island 3 to the island 4            |                           2,3,4                           |                             1,3,3                              |                             0,0,0,0                              |
| 11 | Make the passenger get off the ship 3                        |                           2,3,4                           |                             1,3,3                              |                             0,0,0,0                              |

We can transport a passenger from the island 3 to the island 2 as follows.

| #  | Operation                                                     | The islands <br>where the <br>ships are <br>anchored | The numbers <br>of security <br>guards on <br>the ships | The numbers <br>of security <br>guards on <br>the islands |
| :--: | :------------------------------------------------------------ | :----------------------------------------------------------: | :------------------------------------------------------------: | :------------------------------------------------------------: |
| -  | -                                                             |                           2, 2, 4                           |                             2, 2, 3                              |                             0, 0, 0, 0                              |
| 1  | Make one security guard get off <br>the ship 1         |                           2, 2, 4                           |                             1, 2, 3                              |                             0, 1, 0, 0                              |
| 2  | Make one security guard get on <br>the ship 2          |                           2, 2, 4                           |                             1, 3, 3                              |                             0, 0, 0, 0                              |
| 3  | Move the ship 2 from the island 2 to <br>the island 3 |                           2, 3, 4                           |                             1, 3, 3                              |                             0, 0, 0, 0                              |
| 4  | Make a passenger get on the ship 2                    |                           2, 3, 4                           |                             1, 3, 3                              |                             0, 0, 0, 0                              |
| 5  | Move the ship 2 from the island 3 to <br>the island 2 |                           2, 2, 4                           |                             1, 3, 3                              |                             0, 0, 0, 0                              |
| 6  | Make the passenger get off the ship 2                 |                           2, 2, 4                           |                             1, 3, 3                              |                             0, 0, 0, 0                              |

![](_page_4_Picture_0.jpeg)

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.

| Sample Input 2 | Sample Output 2 |
| :------------- | :------------- |
| `4 3 1`        | `7`            |
| `2 1 3 2`      | `5`            |
| `1 2`          |                |
| `2 3`          |                |
| `3 4`          |                |

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.

| Sample Input 3 | Sample Output 3 |
| :------------- | :------------- |
| `3 3 0`        | `2`            |
| `1 1 1`        |                |
| `1 2`          |                |
| `1 3`          |                |
| `2 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.

![](_page_5_Picture_0.jpeg)

This sample input satisfies the constraints of Subtasks 4, 5, 6, 7.

| Sample Input 4  | Sample Output 4 |
| :-------------- | :-------------- |
| `8 7 0`         | `14`            |
| `2 2 2 2 2 2 2 2` |                 |
| `1 2`           |                 |
| `2 3`           |                 |
| `3 4`           |                 |
| `4 5`           |                 |
| `5 6`           |                 |
| `6 7`           |                 |
| `7 8`           |                 |

This sample input satisfies the constraints of all the subtasks.

| Sample Input 5          | Sample Output 5 |
| :---------------------- | :-------------- |
| `8 7 0`                   | `245`           |
| `16 39 36 23 15 48 23 56` |                 |
| `1 2`                     |                 |
| `1 3`                     |                 |
| `2 4`                     |                 |
| `2 5`                     |                 |
| `3 6`                     |                 |
| `3 7`                     |                 |
| `7 8`                     |                 |

This sample input satisfies the constraints of Subtasks 3, 4, 5, 6, 7.

![](_page_6_Picture_0.jpeg)

| Sample Input 6                          | Sample Output 6 |
| :-------------------------------------- | :-------------- |
| `10 13 4`                                 | `3139`            |
| `314 159 265 358 979 323 846 264 338 327` | `2901`            |
| `1 2`                                     | `2722`            |
| `1 4`                                     | `2567`            |
| `2 3`                                     | `2461`            |
| `2 5`                                     |                 |
| `3 6`                                     |                 |
| `4 5`                                     |                 |
| `4 7`                                     |                 |
| `5 6`                                     |                 |
| `5 8`                                     |                 |
| `6 9`                                     |                 |
| `7 8`                                     |                 |
| `8 9`                                     |                 |
| `9 10`                                    |                 |

This sample input satisfies the constraints of Subtasks 5, 6, 7.

Starter code: