题目描述

FUS公司是一家大型网络公司，总共拥有n台服务器。每一台服务器都有一个limit值，表示这台服务器的最大连接限制。在这n台服务器中，只有n-1条光纤线路连接，保证任意两台服务器可以互相通信。随着公司的发展、用户的增加，服务器的负担越来越重，一些服务器无法胜任任务，一些光纤也趋于老化。因此FUS常常对服务器进行一些调整： 更新操作：选中两个服务器x、y，用一条新的光纤连接它们，形成一个环。这时环上“加入时间”最早的光纤会被断开废弃。 修改操作：修改一个服务器的limit值，可以增大或减小，以胜任业务。 在用户访问时，FUS会智能选择服务器的处理。如果用户访问的内容在x到y服务器的路径上，FUS会自动分配一个k值，令x到y路径上limit值第k小的服务器服务用户。 FUS希望你能帮他实现这些功能。 （简化版：动态维护关于加入时间的最大生成树，带点权修改，多次询问树上给定两点间路径k小值）

输入格式

第1行2个整数，n、m，表示服务器的数量和边的数量。 第2行n个整数，limit[1]到limit[n]，0<=limit[i]<=10^6，表示n个服务器的初始连接限制。 接下来n-1行，表示初始的n-1条光纤。这些光纤的输入顺序就是它们的加入时间顺序。 接下来m行，每行3个整数k、x、y，表示一个操作，总共有3种： （1）k=-1，1<=x,y<=n，x不等于y，表示更新操作，连接x、y光纤，并断开环上最早加入的光纤； （2）k=0，1<=x<=n，0<=y<=10^6，表示修改操作，将x服务器的limit值修改为y； （3）1<=k<=n，1<=x,y<=n，x不等于y，表示一个用户访问的内容在x到y服务器的路径上，要求取limit值第k小的服务器服务用户。 对于第3种操作，保证k不超过x到y路径上的服务器数，也就是保证存在limit值第k小的服务器。

输出格式

对于每一个第3种操作，输出一个数，表示x到y路径上limit值第k小的服务器的limit值。

10 4
1 2 3 4 5 6 7 8 9 10
1 2
2 3
2 4
2 5
3 6
3 7
1 8
8 9
9 10
-1 1 10
0 2 100002
2 2 8
3 6 5

8
6

提示

样例解释： 第1个操作，更新操作，用光纤连接了1、10服务器，断开了1、8服务器之间的光纤。 第2个操作，修改操作，将2的limit值从2修改成了100002。 第3个操作，2到8之间的路径为2-1-10-9-8，limit值分别为100002、1、10、9、8，因此第2小的limit值为8。 第4个操作，6到5之间的路径为6-3-2-5，limit值分别为6、3、100002、5，因此第3小的limit值为6。 数据范围： 本题有4种类型的数据。 类型一（10%）：n=m=1000 类型二（20%）：n=m=50000，0<=k<=n（即不存在更新操作） 类型三（30%）：n=m=50000，保证询问的路径长度之和小于10^8。 类型四（40%）：n=m=100000 对于100%的数据，满足2<=n,m<=100000、每时每刻的limit值<=10^6。

题目来源

By immortalCO