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

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 76
作問者 :

Thistle / テスター :

Rho

10 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

入力

出力

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

入力

出力

86
86
91

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

yukicoder

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

問題文

入力

出力

サンプル

サンプル1

入力

出力

サンプル2

入力

出力