K - 警備員 (Security Guard) Editorial /

Time Limit: 3 sec / Memory Limit: 1024 MiB

Score: 100 points

Problem Statement

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.


Input

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

Output

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.


Constraints

  • 2 \le N \le 200\,000.
  • N - 1 \le M \le 400\,000.
  • 0 \le Q \le 200\,000.
  • 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.

Subtasks

  1. (12 points) 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 points) M = N - 1, Q = 0, A_j = j, B_j = j + 1 (1 \le j \le M).
  3. (12 points) M = N - 1, Q = 0.
  4. (13 points) Q = 0.
  5. (8 points) N \le 16.
  6. (18 points) N \le 3\,000.
  7. (24 points) No additional constraints.

Sample Input 1

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

Sample Output 1

7

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.

# Operation The islands where the ships are anchored The numbers of security guards on the ships The numbers of security guards on 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 where the ships are anchored The numbers of security guards on the ships The numbers of security guards on the islands
- - 2, 2, 4 2, 2, 3 0, 0, 0, 0
1 Make one security guard get off the ship 1 2, 2, 4 1, 2, 3 0, 1, 0, 0
2 Make one security guard get on the ship 2 2, 2, 4 1, 3, 3 0, 0, 0, 0
3 Move the ship 2 from the island 2 to 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 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

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

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

Sample Output 2

7
5

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

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

Sample Output 3

2

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.


Sample Input 4

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

Sample Output 4

14

This sample input satisfies the constraints of all the subtasks.


Sample Input 5

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

Sample Output 5

245

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


Sample Input 6

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

Sample Output 6

3139
2901
2722
2567
2461

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

配点 : 100 点

問題文

JOI 国には N 個の島があり,1 から N までの番号が付けられている.それぞれの島には治安の悪さを表す数値が定められており,島 i (1 \leqq i \leqq N) の治安の悪さは S_i である.

JOI 国での主な交通手段は,2 つの島の間を直通で結ぶ船である.船は M 隻あり,1 から M までの番号が付けられている.船 j (1 \leqq j \leqq M) は島 A_j と島 B_j の間を行き来している.船は需要に応じて好きなタイミングで行き来させることができる.どの島から他のどの島へもいくつかの船を用いて到達することができる.

また,JOI 国では新たに運航する船を何隻か増やす予定である.それらの船についてはその船が行き来する 2 つの島を自由に選ぶことができる.

ある日,停泊中の船が襲撃される事件が起こったため,JOI 国の K 首相は,新たに運航する船を増やすと同時に,船の運航に以下のセキュリティ条件を課すことにした.

  • 船が島 i (1 \leqq i \leqq N) に停泊している間,その船に警備員が S_i 人以上乗船していなければならない.

しかし,警備員を雇うのにはコストがかかるため,雇う警備員の数はできるだけ少なくしたい.このとき,「どの島から他のどの島へもいくつかの船を用いて到達することができる」ままである限り,運航している船のうちいくつかを廃止してもよい.

したがって,新たに運航する船の数を k 隻としたとき,以下のようにして船を運航することになる.

  1. 新たに運航する k 隻の船それぞれについて,その船が行き来する 2 つの島を決定する.
  2. 船のうちいくつかを選び(0 個でもよい),それらの船を廃止する.このとき,新たに運航する船を廃止しても構わない.
  3. 運航するそれぞれの船に警備員を何人か乗せ,その船が行き来する 2 つの島のうちどちらかに停泊させる.このとき,以下の条件を満たさなければならない.

条件 どの 2 つの島 u, v (1 \leqq u \leqq N,1 \leqq v \leqq N) が指定されたとしても,以下の行動を繰り返すことで,セキュリティ条件を満たしたまま客を島 u から島 v に移動させることができる.

  • 客や警備員を,ある島からその島に停泊している船に乗せる.
  • 客や警備員を,ある島に停泊している船からその島に降ろす.
  • ある島に停泊している船を,その船が行き来するもう一方の島に向かわせ停泊させる.

予算の関係上,新たに増やすことのできる船の数は最大で Q 隻である.そこで K 首相は,各 k (0 \leqq k \leqq Q) に対して,新たに増やす船の数が k 隻であるときに必要となる警備員の人数の最小値を知りたい.

島と船の航路,新たに増やすことのできる船の数の情報が与えられたとき,それぞれの k に対して,必要となる警備員の人数の最小値を求めるプログラムを作成せよ.


入力

入力は以下の形式で標準入力から与えられる.

N M Q
S_1 S_2 \cdots S_N
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

標準出力に Q + 1 行で出力せよ.k + 1 行目 (0 \leqq k \leqq Q) には,新たに増やす船の数が k 隻のときに必要となる警備員の人数の最小値を出力せよ.


制約

  • 2 \leqq N \leqq 200\,000.
  • N - 1 \leqq M \leqq 400\,000.
  • 0 \leqq Q \leqq 200\,000.
  • 1 \leqq S_i \leqq 10^9 (1 \leqq i \leqq N).
  • 1 \leqq A_j < B_j \leqq N (1 \leqq j \leqq M).
  • (A_x, B_x) \neq (A_y, B_y) (1 \leqq x < y \leqq M).
  • どの島から他のどの島へもいくつかの船を用いて到達することができる.
  • 入力される値はすべて整数である.

小課題

  1. (12 点) M = N - 1,Q = 0,S_i \leqq 2 (1 \leqq i \leqq N),A_j = j,B_j = j + 1 (1 \leqq j \leqq M).
  2. (13 点) M = N - 1,Q = 0,A_j = j,B_j = j + 1 (1 \leqq j \leqq M).
  3. (12 点) M = N - 1,Q = 0.
  4. (13 点) Q = 0.
  5. (8 点) N \leqq 16.
  6. (18 点) N \leqq 3\,000.
  7. (24 点) 追加の制約はない.

入力例 1

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

出力例 1

7

新たに増やす船の数が 0 隻のとき,必要な警備員の人数は 7 人である.例えば,次のようにして警備員 7 人で条件を満たすことができる.

  • 船 1 を最初,島 2 に停泊させ,2 人の警備員を乗せる.
  • 船 2 を最初,島 2 に停泊させ,2 人の警備員を乗せる.
  • 船 3 を最初,島 4 に停泊させ,3 人の警備員を乗せる.

具体例として,以下の 2 つの場合に客の移動を行うことができることを説明する.

  • 島 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, 2, 3 0, 0, 0, 0
2 客を船 1 に乗せる 1, 2, 4 2, 2, 3 0, 0, 0, 0
3 船 1 を島 1 から島 2 へ向かわせる 2, 2, 4 2, 2, 3 0, 0, 0, 0
4 警備員 1 人と客を船 1 から降ろす 2, 2, 4 1, 2, 3 0, 1, 0, 0
5 警備員 1 人と客を船 2 に乗せる 2, 2, 4 1, 3, 3 0, 0, 0, 0
6 船 2 を島 2 から島 3 へ向かわせる 2, 3, 4 1, 3, 3 0, 0, 0, 0
7 客を船 2 から降ろす 2, 3, 4 1, 3, 3 0, 0, 0, 0
8 船 3 を島 4 から島 3 へ向かわせる 2, 3, 3 1, 3, 3 0, 0, 0, 0
9 客を船 3 に乗せる 2, 3, 3 1, 3, 3 0, 0, 0, 0
10 船 3 を島 3 から島 4 へ向かわせる 2, 3, 4 1, 3, 3 0, 0, 0, 0
11 客を船 3 から降ろす 2, 3, 4 1, 3, 3 0, 0, 0, 0

また,島 3 から島 2 への客の移動は次の表のようにして実現できる.

# 行動 各船が停泊する島 各船の警備員数 各島の警備員数
- - 2, 2, 4 2, 2, 3 0, 0, 0, 0
1 警備員 1 人を船 1 から降ろす 2, 2, 4 1, 2, 3 0, 1, 0, 0
2 警備員 1 人を船 2 に乗せる 2, 2, 4 1, 3, 3 0, 0, 0, 0
3 船 2 を島 2 から島 3 へ向かわせる 2, 3, 4 1, 3, 3 0, 0, 0, 0
4 客を船 2 に乗せる 2, 3, 4 1, 3, 3 0, 0, 0, 0
5 船 2 を島 3 から島 2 へ向かわせる 2, 2, 4 1, 3, 3 0, 0, 0, 0
6 客を船 2 から降ろす 2, 2, 4 1, 3, 3 0, 0, 0, 0

6 人以下の警備員で条件を満たすことは不可能なので,7 を出力する.

この入力例は小課題 2, 3, 4, 5, 6, 7 の制約を満たす.


入力例 2

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

出力例 2

7
5

新たに増やす船の数が 0 隻のとき,入力例 1 と同様に,必要な警備員の人数は 7 人である.

新たに増やす船の数が 1 隻のとき,必要な警備員の人数は 5 人である.例えば,次のようにして警備員 5 人で条件を満たすことができる.

  • 新たに島 2 と島 4 の間を行き来する船を運航させる.(以下,この船を船 4 と書く)
  • 船 3 を廃止する.
  • 船 1 を最初,島 2 に停泊させ,2 人の警備員を乗せる.
  • 船 2 を最初,島 2 に停泊させ,1 人の警備員を乗せる.
  • 船 4 を最初,島 2 に停泊させ,2 人の警備員を乗せる.

この入力例は小課題 5, 6, 7 の制約を満たす.


入力例 3

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

出力例 3

2

新たに増やす船の数が 0 隻のとき,必要な警備員の人数は 2 人である.例えば,次のようにして警備員 2 人で条件を満たすことができる.

  • 船 3 を廃止する.
  • 船 1 を最初,島 1 に停泊させ,1 人の警備員を乗せる.
  • 船 2 を最初,島 1 に停泊させ,1 人の警備員を乗せる.

この入力例は小課題 4, 5, 6, 7 の制約を満たす.


入力例 4

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

出力例 4

14

この入力例はすべての小課題の制約を満たす.


入力例 5

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

出力例 5

245

この入力例は小課題 3, 4, 5, 6, 7 の制約を満たす.


入力例 6

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

出力例 6

3139
2901
2722
2567
2461

この入力例は小課題 5, 6, 7 の制約を満たす.


Source Name

JOI 2022/2023 春季トレーニング Contest Day4 問題2