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) に背丈が H j のジョイキビを植える．その後 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

入力
入力は以下の形式で標準入力から与えられる．入力される値はすべて整数である．

NL
A1 B1
A2 B2..
.
AN−1 BN−1
H1H2..
.
HN
Q(Query 1)(Query 2)..
.
(Query Q)
各 (Query k) (1 ≦ k ≦ Q) にはいくつかの整数が空白区切りで書かれている．そのうち 1 個目の整数を T kとすると，この行の内容は以下のいずれかである．

• T k = 1 のとき，この行には続いて 3 個の整数 Xk , Dk , Wk がこの順に書かれている．これは JOI 君が k
日目に取る行動がタイプ 1 であり，土地 Xk から距離 Dk 以下の範囲にある土地に水を与え，水が与えられた土地に生えているジョイキビの背丈が Wk 倍になることを表す．

• T k = 2 のとき，この行には続いて 1 個の整数 Xk が書かれている．これは JOI 君が k 日目に取る行動がタイプ 2 であり，土地 Xk に生えているジョイキビの背丈を調べることを表す．

出力タイプ 2 の行動，すなわち，T k = 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 ≦ H j ≦ L − 1 (1 ≦ j ≦ N)．
• 1 ≦ Q ≦ 400 000．
• T k は 1, 2 のいずれかである (1 ≦ k ≦ Q)．
• T k = 1 のとき，1 ≦ Xk ≦ N ，0 ≦ Dk ≦ 40，0 ≦ Wk ≦ L − 1 (1 ≦ k ≦ Q)．
• T k = 2 のとき，1 ≦ Xk ≦ N (1 ≦ k ≦ Q)．

小課題
1. (3 点) N ≦ 1 000，Q ≦ 1 000．
2. (9 点) T k = 1 のとき，Dk ≦ 1 (1 ≦ k ≦ Q)．
3. (29 点) T k = 1 のとき，Dk ≦ 2 (1 ≦ k ≦ Q)．
4. (12 点) T k = 1 のとき，Wk = 0 (1 ≦ k ≦ Q)．
5. (30 点) T k = 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

出力例 14 741 222 323 4111141412111 2 1 2
1 1 0 2
2 12 22 32 41 4 10 2
2 12 22 32 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

出力例 26 1045 611 241 482 623 6923491101 5 1 72 41 4 1 91 5 0 72 1
1 1 1 31 6 1 42 52 42 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 TrialMarch 20–23, 2022 (Komaba, Tokyo)
Contest 3 – Sprinkler
入力例 3

出力例 38 105

1 30

3 50

4 736 704 50

7 80

2 458646293111 2 2 02 1
1 6 1 02 42 61 5 2 0
2 8
1 7 2 02 6
2 7
2 4
この入力例は小課題 1, 3, 4, 6 の制約を満たす．

スプリンクラー– 6 / 6