被秀逗了。。。。
考虑不能都成三角形的情况，就是类似于斐波拉契数列，而在int内的只有46个所以每一次先特判，如果大于46直接输出Y否则无脑暴力莽一波。
其实一开始还是想到了去找不能组成三角形的情况，但是至于斐波拉契。。。我擦，完全没想到
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define maxn 100021 #define LL long long using namespace std; int head[maxn],tot=1,h[maxn],n,q[55],cnt,val[maxn],fa[maxn],Q,f[maxn][21]; struct edge{int v,next;}e[maxn]; void adde(int a,int b){e[tot].v=b,e[tot].next=head[a];head[a]=tot++;} void dfs(int u){ h[u]=h[fa[u]]+1,f[u][0]=fa[u]; for(int i=1;i<=17;i++)f[u][i]=f[f[u][i-1]][i-1]; for(int i=head[u];i;i=e[i].next){ dfs(e[i].v); } } int lca(int a,int b){ if(h[a]>h[b])swap(a,b); for(int i=17;i>=0;i--)if(h[f[b][i]]>=h[a])b=f[b][i]; if(a==b)return a; for(int i=17;i>=0;i--){ if(f[a][i]==f[b][i])continue; a=f[a][i],b=f[b][i]; }return f[a][0]; } void solve(){ sort(q+1,q+1+cnt); for(int i=3;i<=cnt;i++){ if((LL)q[i]<(LL)q[i-1]+q[i-2]){puts("Y");return;} }puts("N"); } int main(){ scanf("%d%d",&n,&Q); for(int i=1;i<=n;i++)scanf("%d",val+i); for(int a,b,i=1;i<n;i++){ scanf("%d%d",&a,&b); fa[b]=a;adde(a,b); }dfs(1);int pos,a,b; while(Q--){ scanf("%d%d%d",&pos,&a,&b); if(pos==1)val[a]=b; else{ int g=lca(a,b); if(h[a]+h[b]-h[g]*2+1>46)puts("Y"); else{ cnt=0; while(a!=g){q[++cnt]=val[a];a=fa[a];} while(b!=g){q[++cnt]=val[b];b=fa[b];} q[++cnt]=val[g]; solve(); } } } return 0; }
