bzoj#P3251. 树上三角形

树上三角形

题目描述

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

输入格式

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

然后 n1n-1 行,每行 22 个整数 aabb,表示 aabb 的父亲(以 11 为根的情况下)。

然后 qq 行,每行 33 个整数 ttaabb。若 t=0t=0,则询问 (a,b)(a,b)

t=1t=1,则将点 aa 的点权修改为 bb

输出格式

对每个询问输出一行表示答案,“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%100\% 的数据,n,q100000n,q\le 100000,点权范围 [1,2311][1,2^{31}-1]

题目来源

没有写明来源