*由于该问题的时间限制较长,测试用例中不包含输入/输出示例。
問題文
暂时完成游戏制作后,Joisino Onee-chan决定计划下一款游戏。
然后,我决定制作一个带有地形变化的地图的冒险游戏。
以下是Joisino Onee-chan的想法。
本游戏中有N个城市,分别是N-1假设这些书的连接方式允许它们双向传播。
如果是冒险游戏,我想最好绕着城市走一圈,瞄准目标。
这次不用再考虑绕路了。
所以,如果地形发生变化,我想海拔高度很重要。
如果经过高海拔的城镇就能获得稀有物品怎么办?
那么,我是否应该找到我旅途中经过的城市的最高海拔?
如果你想改变地形,改变从某个城镇开始的道路。c诸如更改按照本书可以到达的所有城市的海拔之类的事情。
总而言之,您所需要做的就是处理这两个事件。
-
事件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,事件数 接下来 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