UOJ Logo 黑暗爆炸OJ

DARKBZOJ

#4129. Haruna’s Breakfast

统计 下载数据

Description

 Haruna每天都会给提督做早餐! 这天她发现早饭的食材被调皮的 Shimakaze放到了一棵

树上,每个结点都有一样食材,Shimakaze要考验一下她。
每个食材都有一个美味度,Shimakaze会进行两种操作:
1、修改某个结点的食材的美味度。
2、对于某条链,询问这条链的美味度集合中,最小的未出现的自然数是多少。即mex值。
请你帮帮Haruna吧。

Input

第一行包括两个整数n,m,代表树上的结点数(标号为1~n)和操作数。

第二行包括n个整数a1...an,代表每个结点的食材初始的美味度。
接下来n-1行,每行包括两个整数u,v,代表树上的一条边。
接下来m 行,每行包括三个整数
0 u x 代表将结点u的食材的美味度修改为 x。
1 u v 代表询问以u,v 为端点的链的mex值。

Output

对于每次询问,输出该链的mex值。

Sample Input

10 10
1 0 1 0 2 4 4 0 1 0
1 2
2 3
2 4
2 5
1 6
6 7
2 8
3 9
9 10
0 7 14
1 6 6
0 4 9
1 2 2
1 1 8
1 8 3
0 10 9
1 3 5
0 10 0
0 7 7

Sample Output

0
1
2
2
3

Hint

1<=n<=5*10^4


1<=m<=5*10^4

0<=ai<=10^9

Source