No.1030 だんしんぐぱーりない

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 67
作問者 : ThistleThistle / テスター : RhoRho
5 ProblemId : 4172 / 出題時の順位表
問題文最終更新日: 2020-04-17 23:33:46

問題文

JOI国には$N$ 個の町がある。これらの町には活気という値が定まっている。$i$ 番目の町の活気は $C_i$ である。
また、これらの町は $N-1$ 本の一方向にしか行くことのできない道でつながっている。$i$本目の辺は町$E_i$と$F_i$をこの向きに結んでいる。
JOI国は頂点$1$ を根とする根付き木となっていて、全ての辺は根の方向へ向き付けられている。

ビ太郎は、こんなJOI国に住む一匹のビーバーであり、パーティーが大好きである。ビ太郎の番号は $1$ である。
また、彼には $2$ ~ $K$ までの番号が付いた $K-1$ 人の親族がいて、彼らも全員パーティーが大好きである。
最初、 $i$ 番目のビーバーは町 $A_i$ に住んでいる。

ビ太郎達は定期的に、以下の条件を満たすようにパーティーを開催する。

  • パーティーには、$L \leq x \leq R$ を満たす番号のビーバーを招待する。
  • 会場は、上記のすべてのビーバーにとって到達可能な町にする。
  • 上の条件を満たす町のうち、活気が最大の町が選ばれる。
  • パーティーが終了した後、すべてのビーバーはおうちに帰る。
また、彼らはとても活動的なので、よく引っ越しをしている。

さて、ビ太郎は今、$P$ 回のパーティーを開こうと画策している。 $i$ 回目のパーティーは、ビーバー $L_i \leq x \leq R_i$を招待して行われる。

また、ビ太郎にはタイムリープ能力があるので、いつ引っ越しが起こるかを把握することができる。
引っ越しは $Q-P$ 回行われる予定である。 $i$ 回目の引っ越しでは、ビーバー $X_{i}$ が町 $Y_{i}$ に引っ越す予定である。

これらの $Q$ 回のイベントは時系列順に以下のようにして与えられる。
  • $T_i=1$ の時 : ビーバー $X_{i}$が町 $Y_{i}$ に引っ越すクエリが与えられる。
  • $T_i=2$ の時 : ビーバー $L_i$ ~ $R_i$ を招待してパーティーを開催する。

あなたの仕事は、パーティーを首を長くして待っているビ太郎のため、それぞれのパーティーが行われる町の活気を求める事である。

入力

$N\ K\ Q$
$C_{1}\ C_{2}\ \dots\ C_{N}$
$A_{1}\ A_{2}\ \dots\ A_{K}$
$E_{1}\ F_{1}$
$E_{2}\ F_{2}$
$\dots$
$E_{N-1}\ F_{N-1}$
$T_{1}\ \dots $
$\dots\ $
$T_{Q}\ \dots $

入力は全て整数
$1 \leq\ N,K,Q \leq\ 10^{5}$
$1 \leq\ C_{i} \leq\ 10^{9}$
$1 \leq\ A_{i} \leq\ N$
辺を順に辿っていくと頂点1にたどり着く
与えられるグラフは有向木である
$1 \leq T_{i} \leq 2$
$T_i=1$の時、クエリは以下の形式で与えられる。

$1\ X_i\ Y_i$     
$1 \leq\ X_{i} \leq\ K$
$1 \leq\ Y_{i} \leq\ N$
$T_i=2$の時、クエリは以下の形式で与えられる。
$2\ L_i\ R_i$    
$1 \leq\ L_{i}\ \leq\ R_{i} \leq\ K$

出力

パーティーが開かれる町の活気を出力し、最後に改行してください。

サンプル

サンプル1
入力
5 2 5
1 2 3 4 5
3 4
2 1
3 2
4 2
5 1
2 1 2
1 1 4
2 1 2
1 2 5
2 1 2
出力
2
4
1

1つ目のクエリでは、ビーバー1~2をパーティーに招待する。彼らが全員行きつけるのは町1,2なので、町1,2の活気の最大値である2を出力する。
2つ目のクエリでは、ビーバー1が都市4に引っ越す。
3つ目のクエリでは、ビーバー1~2をパーティーに招待する。彼らが全員行きつけるのは町1,2,4なので、町1,2,4の活気の最大値である4を出力する。
4つ目のクエリでは、ビーバー2が都市5に引っ越す。
5つ目のクエリでは、ビーバー1~2をパーティーに招待する。彼らが全員行きつけるのは町1のみなので、町1の活気である1を出力する。

サンプル2
入力
3 4 5
86 91 20
3 3 1 2
3 1
2 1
1 3 1
2 2 3
1 3 2
2 2 2
2 3 3
出力
86
86
91

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。