【题解】
算是个思维题。。
题目数据范围很大，而是否能组成三角形这种信息也无法用数据结构维护，那怎么办呢？
我们可以发现，如果想要一个数列任意三项不能组成三角形且各项尽量小，这个数列就是一个斐波那契数列。而本题中点权范围为int范围内，我们可以发现在int范围内斐波那契数列只有46项。
那么如果给出的链上面的点数大于50项，就一定存在三个点可以组成三角形。如果链上的点数小于50，我们直接排序后判断即可。
1 #include<cstdio> 2 #include<algorithm> 3 #define rg register 4 #define N 100010 5 using namespace std; 6 int n,m,tot,val[N],tmp[N],fa[N],last[N],dep[N]; 7 struct edge{ 8 int to,pre; 9 }e[N<<1]; 10 inline int read(){ 11 int k=0,f=1; char c=getchar(); 12 while(c<'0'||c>'9')c=='-'&&(f=-1),c=getchar(); 13 while('0'<=c&&c<='9')k=k*10+c-'0',c=getchar(); 14 return k*f; 15 } 16 void dfs(int x){ 17 for(rg int i=last[x],to;i;i=e[i].pre) 18 dep[to=e[i].to]=dep[x]+1,dfs(to); 19 } 20 inline bool query(int x,int y){ 21 int cnt=0; 22 while(cnt<50){ 23 if(dep[x]<dep[y]) swap(x,y); 24 tmp[++cnt]=val[x]; 25 if(x==y) break; 26 x=fa[x]; 27 } 28 if(cnt>=50) return 1; 29 sort(tmp+1,tmp+1+cnt); 30 for(rg int i=1;i<=cnt-2;i++) 31 if(tmp[i]>tmp[i+2]-tmp[i+1]) return 1; 32 return 0; 33 } 34 int main(){ 35 n=read(); m=read(); 36 for(rg int i=1;i<=n;i++) val[i]=read(); 37 for(rg int i=1;i<n;i++){ 38 int x=read(),y=read(); 39 e[++tot]=(edge){y,last[x]}; last[x]=tot; 40 fa[y]=x; 41 } 42 dfs(dep[1]=1); 43 while(m--){ 44 int opt=read(),x=read(),y=read(); 45 if(opt==0) puts(query(x,y)?"Y":"N"); 46 else val[x]=y; 47 } 48 return 0; 49 }