bzoj#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
提示
对于 的数据,,点权范围 。
题目来源
没有写明来源