BZOJ3251: 树上三角形

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 667  Solved: 275
[Submit][Status][Discuss]

Description

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

Input

第一行两个整数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

Output

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

Sample Input

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

Sample Output

N
Y
Y
N

HINT

对于100%的数据,n,q<=100000,点权范围[1,231-1]

Solution

这题点权范围为Int,我们发现不能构成三角形的数列为菲波那切数列(1,1,2,3,5……),所以到第47项时已经超过了Int,所以我们当点的个数大于47个时(代码里写的是50),就可以直接输出Y了。否则我们便暴力即可。

 

点赞

发表评论

您的电子邮箱地址不会被公开。