7251: BZOJ3251：树上三角形

给定一大小为n的有点权树，每次询问一对点(u,v)，问是否能在u到v的简单路径上取三个点权，以这三个权值为边长构成一个三角形。同时还支持单点修改。  

输入格式

第一行两个整数n、q表示树的点数和操作数 第二行n个整数表示n个点的点权 以下n-1行，每行2个整数a、b，表示a是b的父亲（以1为根的情况下） 以下q行，每行3个整数t、a、b 若t=0，则询问(a,b) 若t=1，则将点a的点权修改为b

输出格式

对每个询问输出一行表示答案，“Y”表示有解，“N”表示无解。

样例输入

5 5
1 2 3 4 5
1 2
2 3
3 4
1 5
0 1 3
0 4 5
1 1 4
0 2 5
0 2 3

样例输出

N
Y
Y
N

提示

对于100%的数据，n,q<=100000，点权范围[1,231-1]
 

题目来源

没有写明来源