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




可复制的 PDF 提取文本
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Mergers
合併(Mergers)
JOI 合衆国にはN 個の都市があり,1 からN までの番号が付けられている.また,JOI 合衆国にはN −1
本の国道がある.i 番目(1 ≦i ≦N −1) の国道は都市Ai と都市Bi を双方向に結んでいる.どの都市からど
の都市へもいくつかの国道を通ることで行くことができる.
現在,JOI 合衆国はK 個の州に分けられており,1 からK までの番号が付けられている.都市j (1 ≦j ≦N)
は州S j に属している.また,どの州も少なくとも1 つの都市を含む.
JOI 合衆国の大統領であるK 理事長は,この国が分裂しないか心配している.次の条件が満たされるよう
に,すべての都市を2 つのグループX, Y に分けることができるとき,JOI 合衆国は分裂可能な状態である
という:
• それぞれの都市は,グループX またはグループY のどちらか一方に属する.
• グループX に属する都市が少なくとも1 個存在する.
• グループY に属する都市が少なくとも1 個存在する.
• どの州についても,その州に属する都市はすべて同じグループに属する.
• グループX に属するどの2 つの都市の間も,グループX に属する都市のみを経由して,国道を通っ
て行き来可能である.
• グループY に属するどの2 つの都市の間も,グループY に属する都市のみを経由して,国道を通っ
て行き来可能である.
K 理事長は,JOI 合衆国を分裂可能でない状態にするために,州の合併を行おうと考えている.1 回の合
併においては,2 つの州が選ばれ,それらが1 つの州にまとめられる.まとめられてできた州に属する都市
は,もとの2 つの州のいずれかに属していた都市である.K 理事長は,なるべく少ない回数の合併を行う
ことで,JOI 合衆国を分裂可能でない状態にしたい.
JOI 合衆国に州が1 個しかないときは,JOI 合衆国は分裂可能でないことに注意せよ.
都市と国道の配置,現在どの都市がどの州に属しているかの状態が与えられたとき,JOI 合衆国を分裂可
能でない状態にするために行う合併の回数の最小値を求めるプログラムを作成せよ.
合併– 1 / 4
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Mergers
入力
入力は以下の形式で標準入力から与えられる.入力の値はすべて整数である.
N K
A1 B1
...
AN−1 BN−1
S 1
...
S N
出力
標準出力に,JOI 合衆国を分裂可能でない状態にするために行う合併の回数の最小値を1 行で出力せよ.
制約
• 1 ≦N ≦500 000.
• 1 ≦K ≦N.
• 1 ≦Ai ≦N (1 ≦i ≦N −1).
• 1 ≦Bi ≦N (1 ≦i ≦N −1).
• どの2 つの都市の間も,いくつかの国道を通ることで行き来可能である.
• 1 ≦S j ≦K (1 ≦j ≦N).
• すべてのk (1 ≦k ≦K) について,S j = k となるj (1 ≦j ≦N) が存在する.
合併– 2 / 4
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Mergers
小課題
1. (10 点) N ≦100,K ≦7.
2. (24 点) N ≦3 000.
3. (14 点) N ≦100 000,K ≦50.
4. (22 点) N ≦100 000.最初の状態において,同じ州に属するどの2 つの都市の間も,100 本以下の国
道を通ることで行き来可能である.
5. (30 点) 追加の制約はない.
入出力例
入力例1 出力例1
5 4 1
1 2
2 3
3 4
3 5
1
2
1
3
4
この入力例では,最初の状態は分裂可能である.例えば,都市1, 2, 3, 4 をグループX とし,都市5 をグ
ループY とすればよい.
州3 と州4 を合併すると分裂可能でなくなる.よって答えは1 である.
合併– 3 / 4
The 18th Japanese Olympiad in Informatics (JOI 2018/2019)
Spring Training Camp/Qualifying Trial
March 19–25, 2019 (Komaba/Yoyogi, Tokyo)
Contest Day 4 – Mergers
入力例2 出力例2
5 4 0
1 2
2 3
3 4
4 5
1
2
3
4
1
この入力例では,最初の状態が分裂可能でない.よって答えは0 である.
入力例3 出力例3
2 2 1
1 2
1
2
合併– 4 / 4