题目描述

给定一大小为 $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\le 100000$，点权范围 $[1,2^{31}-1]$。

题目来源

没有写明来源