BZOJ 3251 树上三角形

发布于 2017-07-11  94 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3251

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


逗比题...

考虑什么情况是不合法的:a+b>=c 那么确定 a、b 后为了满足尽可能多的不合法情况,a、b、c 应当是斐波那契数列中连续三项

斐波那契数列在 int 范围内不超过 50 个,那么如果多于 50 个数显然一定有解,否则随便暴力判断即可

 


一个非常弱的准退役OIER