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






可复制的 PDF 提取文本
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Sprinkler
スプリンクラー(Sprinkler)
JOI 君は,長年にわたる家庭菜園の経験を生かしてIOI 農園を運営することを計画している.
IOI 農園はN 個の土地からなり,1 からN までの番号が付けられている.また,土地と土地の間をつな
ぐN −1 本の道があり,1 からN −1 までの番号が付けられている.道i (1 ≦i ≦N −1) は土地Ai と土地Bi
の間を双方向に結んでいる.どの土地からどの土地へも何本かの道を通ることで移動できる.IOI 農園の各
土地にはスプリンクラーが設置され,その周囲の土地に水を与えることができる.
JOI 君はIOI 農園でジョイキビを育てる予定である.ジョイキビは水を与えると背丈が急激に変化する不
思議な植物である.その一方でジョイキビはあまり丈夫でなく,背丈がL 以上のジョイキビは先端から長
さL の部分が折れてしまう.JOI 君は,この折れた部分を収穫する.
はじめに,JOI 君は土地j (1 ≦j ≦N) に背丈がHj のジョイキビを植える.その後Q 日の間,毎日ジョ
イキビの世話をする.k 日目(1 ≦k ≦Q) には,以下のいずれかの行動をする.
• タイプ1 : 土地Xk のスプリンクラーを使用し,土地Xk から距離Dk 以下の範囲にある土地に水を与
える.水が与えられた土地に生えているジョイキビは,背丈がWk 倍になる.しかし,背丈がL 以上
のジョイキビは先端から長さL の部分が折れてしまうので,最終的に,水が与えられる前の背丈がh
であったジョイキビは,水が与えられた後背丈が「h × Wk をL で割ったあまり」になる.
• タイプ2 : 土地Xk に生えているジョイキビの背丈を調べる.
ここで,土地x (1 ≦x ≦N) と土地y (1 ≦y ≦N) の間の距離とは,土地x から土地y へ道をつたって移動
するために通る必要がある道の本数の最小値のことである.
JOI 君は,ジョイキビが予定通りに育っていることを確認するために,あらかじめタイプ2 の行動で調べ
るジョイキビの背丈を計算しておくことにした.
IOI 農園の情報とJOI 君の計画の情報が与えられたとき,JOI 君がタイプ2 の行動で調べるジョイキビの
背丈を計算するプログラムを作成せよ.
スプリンクラー– 1 / 6
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Sprinkler
入力
入力は以下の形式で標準入力から与えられる.入力される値はすべて整数である.
N L
A1 B1
A2 B2
...
AN−1 BN−1
H1
H2
...
HN
Q
(Query 1)
(Query 2)
...
(Query Q)
各(Query k) (1 ≦k ≦Q) にはいくつかの整数が空白区切りで書かれている.そのうち1 個目の整数をTk
とすると,この行の内容は以下のいずれかである.
• Tk = 1 のとき,この行には続いて3 個の整数Xk, Dk, Wk がこの順に書かれている.これはJOI 君がk
日目に取る行動がタイプ1 であり,土地Xk から距離Dk 以下の範囲にある土地に水を与え,水が与
えられた土地に生えているジョイキビの背丈がWk 倍になることを表す.
• Tk = 2 のとき,この行には続いて1 個の整数Xk が書かれている.これはJOI 君がk 日目に取る行動
がタイプ2 であり,土地Xk に生えているジョイキビの背丈を調べることを表す.
出力
タイプ2 の行動,すなわち,Tk = 2 となるk (1 ≦k ≦Q) それぞれに対して,k 日目時点での土地Xk に生
えているジョイキビの背丈を,標準出力に順に改行区切りで出力せよ.
スプリンクラー– 2 / 6
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Sprinkler
制約
• 2 ≦N ≦200 000.
• 2 ≦L ≦1 000 000 000 (= 109).
• 1 ≦Ai < Bi ≦N (1 ≦i ≦N −1).
• どの土地からどの土地へも何本かの道を通ることで移動できる.
• 0 ≦Hj ≦L −1 (1 ≦j ≦N).
• 1 ≦Q ≦400 000.
• Tk は1, 2 のいずれかである(1 ≦k ≦Q).
• Tk = 1 のとき,1 ≦Xk ≦N,0 ≦Dk ≦40,0 ≦Wk ≦L −1 (1 ≦k ≦Q).
• Tk = 2 のとき,1 ≦Xk ≦N (1 ≦k ≦Q).
小課題
1. (3 点) N ≦1 000,Q ≦1 000.
2. (9 点) Tk = 1 のとき,Dk ≦1 (1 ≦k ≦Q).
3. (29 点) Tk = 1 のとき,Dk ≦2 (1 ≦k ≦Q).
4. (12 点) Tk = 1 のとき,Wk = 0 (1 ≦k ≦Q).
5. (30 点) Tk = 1 のとき,Wk = 2 (1 ≦k ≦Q).
6. (17 点) 追加の制約はない.
スプリンクラー– 3 / 6
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Sprinkler
入出力例
入力例1 出力例1
4 7 4
1 2 2
2 3 2
3 4 1
1 1
1 4
1 4
1 2
11
1 2 1 2
1 1 0 2
2 1
2 2
2 3
2 4
1 4 10 2
2 1
2 2
2 3
2 4
はじめに,JOI 君はすべての土地に背丈が1 のジョイキビを植える.
1 日目には,JOI 君は土地2 のスプリンクラーを使用し,土地2 から距離1 以下である土地1, 2, 3 に生え
ているジョイキビの背丈が2 倍になる.その結果,土地1, 2, 3, 4 に生えているジョイキビの背丈はそれぞれ
2, 2, 2, 1 となる.
2 日目には,JOI 君は土地1 のスプリンクラーを使用し,土地1 から距離0 以下である土地1 に生えて
いるジョイキビの背丈が2 倍になる.その結果,土地1, 2, 3, 4 に生えているジョイキビの背丈はそれぞれ
4, 2, 2, 1 となる.
7 日目には,JOI 君は土地4 のスプリンクラーを使用し,土地4 から距離10 以下である土地1, 2, 3, 4 に
生えているジョイキビの背丈が2 倍になる.その結果,土地1, 2, 3, 4 に生えているジョイキビの背丈はそれ
ぞれ8, 4, 4, 2 となるが,土地1 に生えているジョイキビの背丈が7 以上であるため先端から長さ7 の部分
スプリンクラー– 4 / 6
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Sprinkler
が折れて,最終的にそれぞれ1, 4, 4, 2 となる.
この入力例は小課題1, 5, 6 の制約を満たす.
入力例2 出力例2
6 10 4
5 6 1
1 2 4
1 4 8
2 6 2
3 6
9
2
3
4
9
1
10
1 5 1 7
2 4
1 4 1 9
1 5 0 7
2 1
1 1 1 3
1 6 1 4
2 5
2 4
2 3
1 日目には,JOI 君は土地5 のスプリンクラーを使用し,土地5 から距離1 以下である土地5, 6 に生えて
いるジョイキビの背丈が7 倍になる.その結果,土地5, 6 に生えているジョイキビの背丈はそれぞれ63, 7
となるが,土地5 に生えているジョイキビは背丈が10 未満になるまで先端から長さ10 の部分が折れ続け,
最終的にそれぞれ3, 7 となる.
この入力例は小課題1, 2, 3, 6 の制約を満たす.
スプリンクラー– 5 / 6
The 21st Japanese Olympiad in Informatics (JOI 2021/2022)
Spring Training Camp/Qualifying Trial
March 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Sprinkler
入力例3 出力例3
8 10 5
1 3 0
3 5 0
4 7 3
6 7 0
4 5 0
7 8 0
2 4
5
8
6
4
6
2
9
3
11
1 2 2 0
2 1
1 6 1 0
2 4
2 6
1 5 2 0
2 8
1 7 2 0
2 6
2 7
2 4
この入力例は小課題1, 3, 4, 6 の制約を満たす.
スプリンクラー– 6 / 6