看到这种奇怪的要求，考虑一下推结论
考虑把路径上的点权拿出来排序，变成一个数列，那么显然我们只要考虑相邻连续的 $3$ 个数
发现如果我们贪心构造一个尽量无法构成三角形的数列，那么最小的数列就是斐波那契数列
众所周知斐波那契数列增长很快，第 $50$ 项显然远大于题目给出的点权范围，所以如果 $u,v$ 之间点数大于等于 $50$，那么鸽巢原理一下显然一定能构成三角形
所以如果 $u,v$ 之间点数超过 $50$ 直接输出 $Y$ 即可，否则我们再暴力判断即可
这个实现就一倍增 $LCA$
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7; int fir[N],from[N<<1],to[N<<1],cntt; inline void add(int a,int b) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; } int n,m,a[N]; int dep[N],f[N][21]; void dfs(int x) { dep[x]=dep[f[x][0]]+1; for(int i=1;(1<<i)<=dep[x];i++) f[x][i]=f[f[x][i-1]][i-1]; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(v==f[x][0]) continue; f[v][0]=x; dfs(v); } } int LCA(int x,int y) { if(dep[x]<dep[y]) swap(x,y); for(int i=20;i>=0;i--) if(dep[f[x][i]]>=dep[y]) x=f[x][i]; if(x==y) return x; for(int i=20;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i]; return f[x][0]; } int tmp[57],tot; int main() { n=read(),m=read(); int opt,x,y; for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<n;i++) x=read(),y=read(),add(x,y),add(y,x); dfs(1); for(int i=1;i<=m;i++) { opt=read(); x=read(),y=read(); if(opt==1) { a[x]=y; continue; } int lca=LCA(x,y); if(dep[x]+dep[y]-2*dep[lca]>=50) { printf("Y\n"); continue; } tmp[tot=1]=a[lca]; while(x!=lca) tmp[++tot]=a[x],x=f[x][0]; while(y!=lca) tmp[++tot]=a[y],y=f[y][0]; sort(tmp+1,tmp+tot+1); bool GG=0; for(int i=3;i<=tot;i++) if(1ll*tmp[i-2]+tmp[i-1]>1ll*tmp[i]) { GG=1; break; } if(GG) printf("Y\n"); else printf("N\n"); } return 0; }