logo AlgoBeat OnlineJudge
登录 注册

#103251. [BZOJ 3251] 树上三角形

内存限制:128 MiB 时间限制:10000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

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

输入格式

第一行两个整数 表示树的点数和操作数,然后第二行 个整数表示 个点的点权。

然后 行,每行 个整数 ,表示 的父亲(以 为根的情况下)。

然后 行,每行 个整数 。若 ,则询问

,则将点 的点权修改为

输出格式

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

样例

样例输入 #1

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

样例输出 #1

N
Y
Y
N

数据范围与提示

对于 的数据,,点权范围

没有写明来源