← 返回题目列表

AtCoder · joiopen2020_c

C. 发电厂

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

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

発電所 (Power Plant) - 原题 PDF 第 1 页
原题PDF第1页
発電所 (Power Plant) - 原题 PDF 第 2 页
原题PDF第2页
発電所 (Power Plant) - 原题 PDF 第 3 页
原题PDF第3页
可复制的 PDF 提取文本
The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                                  JOI Open Contest

                                                                       September 6, 2020


                                                                               power

                発電所(Power Plant)



  JOI 発電所にはN 個の基地があり,1 からN までの番号が付いている.これらの基地は,N −1 本の電線
で結ばれている.i 番目(1 ≦i ≦N −1) の電線は基地Ai と基地Bi を双方向に結んでいる.どの基地からど

の基地へも何本かの電線をたどることで移動できる.

  JOI 発電所の各基地には高々1 個の発電機が設置されており,それぞれの発電機はスイッチを持つ.最

初,どの発電機のスイッチもOFF の状態になっている.JOI 発電所の所長であるあなたは,いくつか(0 個

以上) の発電機を選んでそれらの発電機のスイッチを同時にON にすることができる.ただし,発電機は次

のような性質を持っている.

    • 発電機が設置されている3 つの異なる基地x, y, z について,同じ電線を2 回たどることなく,基地

        x, y, z の順番に何本かの電線をたどって移動できるとする.もし基地x の発電機と基地z の発電機の

   スイッチがともにON になっているなら,基地y の発電機は壊れる.

    • スイッチがON になっていて,かつ壊れていない発電機は稼働する.

 あなたは最終的に,稼働している発電機1 個につき1 円の報酬を得ることができる.また,壊れた発電

機1 個につき1 円の修理費を支払わなければならない.報酬の合計から修理費の合計を引いた値が利益と

なる.

  JOI 発電所の基地と電線の配置,発電機の情報が与えられたとき,得られる利益の最大値を求めるプログ

ラムを作成せよ.


入力


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


    N

      A1 B1
                                 ...

      AN−1 BN−1

      S

S は各基地の発電機の有無を表す長さN の文字列である.S の各文字は0,1 のいずれかであり,i 番目の

文字(1 ≦i ≦N) は基地i の発電機を表す.0 はその基地に発電機がないことを,1 はその基地に発電機があ

ることを表す.





                        発電所– 1 / 3

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                                  JOI Open Contest

                                                                       September 6, 2020


                                                                               power



出力

 いくつかの発電機のスイッチをON にしたとき得られる利益の最大値を標準出力に1 行で出力せよ.


制約

    • 1 ≦N ≦200 000.
    • 1 ≦Ai ≦N (1 ≦i ≦N −1).
    • 1 ≦Bi ≦N (1 ≦i ≦N −1).
    • Ai , Bi (1 ≦i ≦N −1).
    • どの2 つの基地の間も,いくつかの電線を通ることで行き来可能である.

    • S は0, 1 からなる,長さN の文字列である.

    • S は1 を1 文字以上含む.


小課題

    1. (6 点) N ≦16.

    2. (41 点) N ≦2 000.

    3. (53 点) 追加の制約はない.


入出力例

  入力例1              出力例1

   6                              3

   2 3

   4 3

   1 3

   3 5

   6 2

   110011

 この入力例では基地1, 2, 5, 6 に発電機が設置されている.

 基地1, 2, 5 の発電機のスイッチをON にすると,基地1, 2, 5 の発電機が稼働する.3 円の報酬が得られ,

修理費は支払わないので3 円の利益を得ることができる.これが利益の最大値であるので3 を出力する.



                        発電所– 2 / 3

The 19th Japanese Olympiad in Informatics (JOI 2019/2020)

                                                                  JOI Open Contest

                                                                       September 6, 2020


                                                                               power


 一方で基地1, 5, 6 の発電機のスイッチをON にすると,基地2 の発電機が壊れ,基地1, 5, 6 の発電機が

稼働する.3 円の報酬が得られ,1 円の修理費を支払うのでこのとき得られる利益は2 円となる.

 また基地1, 2, 5, 6 の発電機のスイッチをON にすると,基地2 の発電機が壊れ,基地1, 5, 6 の発電機が

稼働する.3 円の報酬が得られ,1 円の修理費を支払うのでこのときも得られる利益は2 円となる.


  入力例2              出力例2

   8                              3

   1 2

   3 5

   6 4

   4 5

   5 2

   7 2

   2 8

   11111111


  入力例3                    出力例3

   16                                      5

   7 10

   5 11

   9 4

   14 12

   2 11

   14 16

   4 2

   1 13

   11 3

   7 1

   15 9

   2 1

   11 6

   14 9

   8 9

   0111111001001110




                        発電所– 3 / 3