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]
题目分析
贪心来想 假设你找到了一条最长路径，并且保证在它上面的点权都不能构成三角形。
那么将边权从大到小排序后 点权一定满足 a[i]+a[i+1]==a[i+2]
这是啥 斐波那契数列啊QAQ
我们再来看点权范围 [ int ] 在[ int ]范围内的斐波那契数列的个数为47
这说明：如果询问路径上的点的个数超过了47 那一定会能构成三角形
如果不超47直接暴力就好了 用朴素lca拿路径 如果当前栈内点数大于47直接return
#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
int tot;
int head[110000],to[220000],net[220000];
void add(int x,int y)
{
net[++tot]=head[x];
to[tot]=y;
head[x]=tot;
}
long long val[110000];
int deep[110000],fa[110000];
void dfs(int x)
{
deep[x]=deep[fa[x]]+1;
for(int i=head[x];i;i=net[i])
if(to[i]!=fa[x])
fa[to[i]]=x,dfs(to[i]);
}
long long sta[100];
int ask(int x,int y)
{
sta[0]=0;
while(sta[0]<50&&x!=y)
{
if(deep[x]>deep[y]) sta[++sta[0]]=val[x],x=fa[x];
else sta[++sta[0]]=val[y],y=fa[y];
}
sta[++sta[0]]=val[x];
if(sta[0]>50) return 1;
sort(sta+1,sta+sta[0]+1);
for(int i=1;i<=sta[0]-2;i++)
if((long long)sta[i]+sta[i+1]>sta[i+2]) return 1;
return 0;
}
int q;
int main()
{
scanf("%d%d",&n,&q);
for(int i=1;i<=n;i++) scanf("%lld",&val[i]);
for(int i=1;i<n;i++)
{
int x,y;
scanf("%d%d",&x,&y);
add(x,y),add(y,x);
}
dfs(1);
for(int i=1;i<=q;i++)
{
int tmp,x,y;
long long c;
scanf("%d%d",&tmp,&x);
if(tmp==0)
{
scanf("%d",&y);
if(ask(x,y)) printf("Y\n");
else printf("N\n");
}
else scanf("%lld",&c),val[x]=c;
}
return 0;
}
