神tmWA了8发调了20min才发现输出没回车T T...
首先考虑一段什么样的序列才会是N... 显然最长的形式就是斐波那契，前两数之和等于第三数之和，这样就无法组成三角形并且序列最长。可以发现在int范围内斐波那契数列不会超过50个，所以如果这段路径上节点数超过50个直接输出Y，否则把50个数拉出来排序暴力找是否有三角形就好了。
#include<iostream> #include<cstring> #include<cstdlib> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=500010; struct poi{int too, pre;}e[maxn<<1]; int n, q, ty, x, y, cnt, tot; int a[maxn], d[maxn], fa[maxn], last[maxn], st[maxn]; void read(int &k) { int f=1; k=0; char c=getchar(); while(c<'0' || c>'9') c=='-' && (f=-1), c=getchar(); while(c<='9' && c>='0') k=k*10+c-'0', c=getchar(); k*=f; } inline void add(int x, int y){e[++tot]=(poi){y, last[x]}; last[x]=tot;} void dfs(int x) { d[x]=d[fa[x]]+1; for(int i=last[x], too;i;i=e[i].pre) fa[too=e[i].too]=x, dfs(too); } inline bool query(int x, int y) { int cnt=0; while(cnt<50) { if(d[x]<d[y]) swap(x, y); st[++cnt]=a[x]; if(x==y) break; x=fa[x]; } if(cnt>=50) return 1; sort(st+1, st+1+cnt); for(int i=1;i<=cnt-2;i++) if((ll)st[i]+st[i+1]>st[i+2]) return 1; return 0; } int main() { read(n); read(q); for(int i=1;i<=n;i++) read(a[i]); for(int i=1;i<n;i++) read(x), read(y), add(x, y); dfs(1); for(int i=1;i<=q;i++) { read(ty); read(x); read(y); if(!ty) printf("%s ", query(x, y)?"Y":"N"); else a[x]=y; } }