8129: BZOJ4129:Haruna’s Breakfast
Memory Limit:128 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Haruna每天都会给提督做早餐! 这天她发现早饭的食材被调皮的 Shimakaze放到了一棵
树上,每个结点都有一样食材,Shimakaze要考验一下她。 每个食材都有一个美味度,Shimakaze会进行两种操作: 1、修改某个结点的食材的美味度。 2、对于某条链,询问这条链的美味度集合中,最小的未出现的自然数是多少。即mex值。 请你帮帮Haruna吧。输入格式
第一行包括两个整数n,m,代表树上的结点数(标号为1~n)和操作数。
第二行包括n个整数a1...an,代表每个结点的食材初始的美味度。 接下来n-1行,每行包括两个整数u,v,代表树上的一条边。 接下来m 行,每行包括三个整数 0 u x 代表将结点u的食材的美味度修改为 x。 1 u v 代表询问以u,v 为端点的链的mex值。输出格式
对于每次询问,输出该链的mex值。
样例输入
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
样例输出
0 1 2 2 3
提示
1<=n<=5*10^4
1<=m<=5*10^4 0<=ai<=10^9题目来源
没有写明来源