以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。





可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 4 – Capital City
首都(Capital City)
JOI 国にはN 個の町があり,1 からN までの番号が付けられている.また,JOI 国にはN −1 本の国道が
ある.i 番目(1 ≦i ≦N −1) の国道は町Ai と町Bi を双方向に結んでいる.どの町からどの町へもいくつか
の国道を通ることで行くことができる.
現在,JOI 国はK 個の都市に分けられており,1 からK までの番号が付けられている.町j (1 ≦j ≦N)
は都市C j に属している.また,どの都市も少なくとも1 つの町を含む.
JOI 国の国王であるK 理事長は,どれか1 つの都市を首都に指定することにした.首都となる都市は,国
防上の観点から,以下の条件を満たさなくてはならない:
その都市に含まれるどの2 つの町の間も,その都市に含まれる町のみを通ることで行き来することが
できる.
しかし,K 理事長は,今の都市がいずれもこの条件を満たさず首都を指定することができない可能性があ
ることに気が付いた.
そこで,都市と都市の合併を行うことにした.詳細には,以下の操作を行うことができる:
1 ≦x ≦K, 1 ≦y ≦K かつx , y を満たすx, y を選び,都市y に属しているすべての町を都市x に属
するように変更する.
都市と都市の合併は非常にコストがかかるので,K 理事長は首都として指定する都市には制約を設けず,
合併の回数を出来るだけ少なくしたいと考えている.
JOI 国における町と国道の配置,現在どの町がどの都市に属しているかの状態が与えられるので,必要な
合併な回数の最小値を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力の値はすべて整数である.
N K
A1 B1
...
AN−1 BN−1
C1
...
CN
首都– 1 / 5
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 4 – Capital City
出力
標準出力に,首都を指定するために必要な合併の回数の最小値を1 行で出力せよ.
制約
• 1 ≦N ≦200 000.
• 1 ≦K ≦N.
• 1 ≦Ai ≦N (1 ≦i ≦N −1).
• 1 ≦Bi ≦N (1 ≦i ≦N −1).
• どの2 つの町の間も,いくつかの国道を通ることで行き来可能である.
• 1 ≦C j ≦K (1 ≦j ≦N).
• すべてのk (1 ≦k ≦K) について,C j = k となるj (1 ≦j ≦N) が存在する.
小課題
1. (1 点) N ≦20.
2. (10 点) N ≦2 000.
3. (30 点) どの町も高々2 つの町としか国道で結ばれていない.
4. (59 点) 追加の制約はない.
首都– 2 / 5
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 4 – Capital City
入出力例
入力例1 出力例1
6 3 1
2 1
3 5
6 2
3 4
2 3
1
3
1
2
3
2
入力例1 では,例えば(x, y) = (1, 3) として都市3 を都市1 に対して合併することで,都市1 を首都に指
定することができる.初期状態ではいずれの都市も首都に指定することはできないので,最小回数である1
を出力する.
入出力例1 は小課題1, 2, 4 の制約を満たす.
首都– 3 / 5
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 4 – Capital City
入力例2 出力例2
8 4 1
4 1
1 3
3 6
6 7
7 2
2 5
5 8
2
4
3
1
1
2
3
4
入力例2 は小課題1, 2, 3, 4 の制約を満たす.
首都– 4 / 5
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)
Spring Training Camp/Qualifying Trial
March 20–23, 2020 (Komaba, Tokyo)
Contest Day 4 – Capital City
入力例3 出力例3
12 4 2
7 9
1 3
4 6
2 4
10 12
1 2
2 10
11 1
2 8
5 3
6 7
3
1
1
2
4
3
3
2
2
3
4
4
入力例3 は小課題1, 2, 4 の制約を満たす.
首都– 5 / 5