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



可复制的 PDF 提取文本
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 3 – Meetings 2
ビーバーの会合2 (Meetings 2)
ビーバーの住んでいる島がN 個あり,1 からN までの番号が付けられている.これらの島はN −1 本の双
方向に通行可能な橋で結ばれており,橋には1 からN −1 までの番号が付けられている.橋i (1 ≦i ≦N −1)
は島Ai と島Bi を結んでいる.どの島の間もいくつかの橋を通って移動が可能である.また,それぞれの島
には1 匹のビーバーが住んでいる.
時々,いくつかの島に住むビーバーが,1 つの島に集まって会合を行う.会合に参加するビーバーが決
まったとき,次の条件を満たす島のうちのいずれかで会合が行われる:
集まる際に,会合に参加するビーバーが通る橋の本数の合計が最小となる島.
ただし,ある島に集まる際,各ビーバーは自分の住む島からその島まで,できるだけ少ない本数の橋を通っ
て移動するものとする.
会合に参加するビーバーが決まったとき,会合が行われる可能性のある島が多いほど,ビーバーたちは会
合を楽しみに思う.各会合について,その会合の期待度を,参加するビーバーが決まった時点で会合が行わ
れる可能性のあった島の個数として定める.あなたは,1 以上N 以下の各整数j について,j 匹のビーバー
で行われる会合の期待度の最大値を知りたい.
島の情報が与えられたとき,ありうるすべての参加匹数について,その匹数のビーバーで行われる会合の
期待度の最大値を求めるプログラムを作成せよ.
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N
A1 B1
...
AN−1 BN−1
出力
標準出力にN 行で出力せよ.j 行目(1 ≦j ≦N) には,j 匹のビーバーで行われる会合の期待度の最大値
を出力せよ.
ビーバーの会合2– 1 / 3
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 3 – Meetings 2
制約
• 1 ≦N ≦200 000.
• 1 ≦Ai ≦N (1 ≦i ≦N −1).
• 1 ≦Bi ≦N (1 ≦i ≦N −1).
• Ai , Bi (1 ≦i ≦N −1).
• どの島の間もいくつかの橋を通って移動が可能である.
小課題
1. (4 点) N ≦16.
2. (16 点) N ≦4 000.
3. (80 点) 追加の制約はない.
入出力例
入力例1 出力例1
5 1
1 2 4
2 3 1
4 2 2
3 5 1
例えば,島1 に住むビーバーと島3 に住むビーバーで行われる会合について考える.この2 匹のビーバー
が集まる際に通る橋の本数の合計は,以下のようになる.
• 島1 に集まる場合,島1 に住むビーバーの通る橋の本数は0 本であり,島3 に住むビーバーの通る
橋の本数は2 本である.よって,各ビーバーが通る橋の本数の合計は2 である.
• 島2 に集まる場合,各ビーバーが通る橋の本数の合計は2 である.
• 島3 に集まる場合,各ビーバーが通る橋の本数の合計は2 である.
• 島4 に集まる場合,各ビーバーが通る橋の本数の合計は4 である.
• 島5 に集まる場合,各ビーバーが通る橋の本数の合計は4 である.
よって,この2 匹のビーバーで行われる会合は,島1, 2, 3 で開かれる可能性があり,期待度は3 である.
ビーバーの会合2– 2 / 3
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)
Spring Training Camp/Qualifying Trial
March 20–23, 2021 (Komaba, Tokyo)
Contest Day 3 – Meetings 2
入力例2 出力例2
7 1
1 2 5
2 3 1
3 4 3
4 5 1
2 6 2
3 7 1
ビーバーの会合2– 3 / 3