← 返回题目列表

AtCoder · tkppc2016_j

J. 下一份工作(新游戏)

中文机器翻译题面 查看原题

*由于该问题的时间限制较长,测试用例中不包含输入/输出示例。


問題文

暂时完成游戏制作后,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