#BZOJ3251. 树上三角形
-
ID: 1767
Type: RemoteJudge
1000ms
256MiB
Tried: 0
Accepted: 0
Difficulty: (None)
Uploaded By:
root
树上三角形
No submission language available for this problem.
题目描述
给定一大小为n的有点权树，每次询问一对点(u,v)，问是否能在u到v的简单路径上取三个点权，以这三个权值为边
长构成一个三角形。同时还支持单点修改。
输入格式
第一行两个整数n、q表示树的点数和操作数
第二行n个整数表示n个点的点权
以下n-1行，每行2个整数a、b，表示a是b的父亲（以1为根的情况下）
以下q行，每行3个整数t、a、b
若t=0，则询问(a,b)
若t=1，则将点a的点权修改为b
n,q<=100000，点权范围[1,2^31-1]
输出格式
对每个询问输出一行表示答案，“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