J - 次のお仕事 (New Game) Editorial /

Time Limit: 7.5 sec / Memory Limit: 256 MB

※この問題は時間制限が長いので、テストケースに入出力例を入れていません。

問題文

ひとまずゲーム作りを終えたjoisinoお姉ちゃんは、次のゲームの企画をすることになった。
そして、今度は地形が変わるマップでのアドベンチャーゲームを作ろうと思った。
以下joisinoお姉ちゃんの考えである。

このゲームではN個の街があって、それがN-1本の双方向に通行可能な道で互いに行き来できるようにつながっていることにしよう。
やっぱりアドベンチャーゲームなら街を巡ってゴールを目指すのがいいかな。
今回は遠回りすることは考えなくていいか。
それで、地形が変わるならやっぱり標高が重要かな。
標高が高い街を通るとレアなアイテムがもらえるとかどうだろう？
それなら旅で通る街の標高の最大値を求めればいいかな？
地形を変えるならある街から道をc本以下たどることでたどり着ける街すべての標高を変えるとかだね。

整理すると、この2つのイベントを処理すればいいってことだよね。

  • イベント1
    整数a, b, cが与えられる。
    街aからb本以下の道でたどり着ける街の標高がcになる。
  • イベント2
    整数a, bが与えられる。
    街aから街bまでの最短経路の街の標高の最大値に応じてアイテムがもらえる。

でも、これだとどれぐらいのアイテムをもらえるんだろう？

そこでjoisinoお姉ちゃんは、イベント2において最短経路の街の標高の最大値を求めるプログラムを書くことにした。

入力

入力は以下の形式で標準入力から与えられる。

N Q
E_1
E_2
：
E_N
S_1 G_1
S_2 G_2
：
S_{N-1} G_{N-1}
T_1 A_1 B_1 C_1
T_2 A_2 B_2 C_2
：
T_Q A_Q B_Q C_Q
  • 1行目には、街の数N、イベントの数Qが与えられる。(1 ≦ N ≦ 70000, 1 ≦ Q ≦ 70000)
  • 次のN行のうちi行目には、E_iが与えられ、街iのはじめの標高を表している。(1 ≦ E_i ≦ 10^9)
  • 次のN-1行のうちi行目には、S_i,G_iが与えられ、S_iとG_iが道で結ばれていることを表す。(1 ≦ S_i, G_i ≦ N, S_i ≠ G_i)
  • 次のQ行のうちi行目には、T_i, A_i, B_i, C_iが与えられる。
  • T_i=1の時、イベント1を表し、街A_iからB_i本以下の道でたどり着ける街の標高がC_iになる。(1 ≦ A_i ≦ N, 0 ≦ B_i ≦ 10^9, 1 ≦ C_i ≦ 10^9)
  • T_i=2の時、イベント2を表し、街A_iから街B_iまでの最短経路の街の標高の最大値を出力する。(1 ≦ A_i, B_i ≦ N)
    A_i = B_iの場合は街A_iの標高を出力する。 また、C_iは無視して構わない。

出力

すべてのイベント2について、最短経路の街の標高の最大値を出力せよ。

入力例1

5 5
3
2
5
2
6
1 2
2 3
3 5
3 4
2 1 5 0
1 4 1 7
2 5 2 0
1 3 1 2
2 4 1 0

出力例1

6
7
3

  • クエリ1 : 街1から街5までの最短経路で通る街は1, 2, 3, 5なので、それらの標高3, 2, 5, 6の最大値6を出力する。
  • クエリ2 : 街4から1本の道を通ってたどり着ける街は4, 3なので、それらの標高を7にする。
  • クエリ3 : 街5から街2までの最短経路で通る街は5, 3, 2なので、それらの標高6, 7, 2の最大値7を出力する。
  • クエリ4 : 街3から1本の道を通ってたどり着ける街は3, 2, 4, 5なので、それらの標高を2にする。
  • クエリ5 : 街4から街1までの最短経路で通る街は4, 3, 2, 1なので、それらの標高2, 2, 2, 3の最大値3を出力する。

入力例2

10 10
78
87
33
57
93
49
45
17
56
44
1 2
2 3
1 4
1 5
4 6
3 7
6 8
3 9
6 10
2 2 2 0
1 1 2 59
1 7 1 96
2 7 8 0
2 3 4 0
2 10 4 0
1 8 2 45
1 3 3 24
2 2 1 0
2 6 9 0

出力例2

87
96
96
59
24
45