← 返回题目列表

AtCoder · joisc2021_j

I. 海狸会议 2

中文机器翻译题面 查看原题

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

ビーバーの会合 2 (Meetings 2) - 原题 PDF 第 1 页
原题PDF第1页
ビーバーの会合 2 (Meetings 2) - 原题 PDF 第 2 页
原题PDF第2页
ビーバーの会合 2 (Meetings 2) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 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