小奇的幸运树

小奇的幸运树

问题描述

有一棵 n 个点的树,从 1 到 n 编号。树上的每个点有点权。对于树上的一条路径,如果路径上能选出四个点,以这四个点的权值作为边长能组成四边形,那么小奇认为这是一条幸运路径。
现在有 q 个操作,分为以下两种:
0. 询问一条路径是否是幸运路径。
1. 修改某个点的点权。

输入格式

第一行两个正整数\(n,q\),代表点数和操作数。
第二行\(n\)个正整数,表示点权。
接下来\(n-1\)行,每行有两个整数\(u\),\(v\),代表\(u\),\(v\)之间有一条边。
接下来\(q\)行,每行有三个整数\(t\),\(a\),\(b\),若\(t=0\),表示询问a到b的路径是否是幸运路径,否则表示将点\(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 3 5
0 2 3

样例输出

N Y Y N

提示

对于30%的数据,有\(n,q<=1000\)
对于100%的数据,有\(n,q<=10^5\),点权为小于\(2^31\)的正整数。
如果路径点数小于4,不是幸运路径。

信息

ID
1393
难度
10
分类
模拟 | 数论 | 其他 | 数学 点击显示
标签
(无)
递交数
1
已通过
0
通过率
0%
被复制
1
上传者