给出n,k,以及一个有n个节点的树，每个节点都有一个点权，点权互不相同。k次询问，每次询问询问一个节点，求以该节点为根的子树内是否能以任意三个节点的点权为边构造一个三角形。
1<=n,k<=4e4 , 1<=ai<=1e7
本题是zhx大佬口胡的一道题，上课bb了好久QAQ
以下是本题的回顾与整理！
约定
我们称三个数为“三角形数”，当且仅当以它们为三角形的三条边可以构成三角形
我们称一棵树为“三角形树”，当且仅当这棵树内有一组三角形数
定理1
一棵含有40个以上的节点的子树必定是三角形树
假设这棵树不是三角形树：
设这个子树中的两个最小的点权为a1,a2，这个子树的节点数量为m
则使a1,a2与其他点权不能构成三角形。有a3>=a1+a2。同理，a(x)>=a(x-1)+a(x-2)
得am>=fibo(m-1)a2+fibo(m-2)a1
可以发现 a1,a2>=1
则am>=fibo(m)
当然，fibo(m) 远超出1e7的范围。所以原命题成立。
定理2
对于一个有序数列 A，如果任意相邻三个数不是三角形数，那么这个数列A中没有三角形数。
反证法：
设这个数列A中有一对三角形数 Ax,Ay,Az。为防止歧义，规定x<y<z
那么：
Ax+Ay>Az
现在证明 Ay-1,Ay,Ay+1也是一组三角形数
因为Ay-1>=Ax
Ay+1<Az
所以Ay-1+Ay>Ay+1成立。
因为相邻三个数中有一对三角形数。所以与原始条件相矛盾，所以这个数列中没有三角形数
解法
对于size(x)>=40，我们直接输出有三角形数（定理1）
对于size(x)<40，我们遍历x的子树存在数列里，排序后遍历所有相邻的三个数。如果有，那么肯定有；
如果没有，那么一定没有。（定理2）
基数排序甚至可以卡到 O(qn)！当然这个n实际上是 min(size(x)，40) qwq
至此，本题完结
Code
彩蛋
