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



可复制的 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