#P3251. 树上三角形
树上三角形
树上三角形
题目描述
给定一棵有 个节点的有根树,每个节点有一个点权。操作可以修改一个点的权值,或询问两个节点的简单路径上,能否选择三个不同的节点,使它们的当前点权可以作为一个三角形的三条边长。路径包含两个端点。
输入格式
第一行包含两个整数 ,分别为节点数和操作数。第二行包含 个整数,按编号给出每个节点的初始点权。
接下来 行,每行两个整数 ,表示在以 为根的树中, 是 的父亲。
再接下来 行,每行三个整数 。
- 时,询问从节点 到节点 的路径。
- 时,将节点 的点权修改为 。
输出格式
对每次询问输出一行。存在所求的三个节点时输出 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
数据规模与约定
。点权在 内。