题意:链接方法:神TM脑洞题解析:首先你要有一个很大的脑洞。然后我们开始放开脑洞- -!类斐波那契数列一定不会构成三角形！如果一项等于前两项的和的话，那么我们称它为类斐波那契数列。现在，观察数据范围，2^31-1，这个范围内，，一个类斐波那契数列最多有多少项呢？大概是50.也就是说，如果对于一个询问，点的个数超过了50，那么一定能构成三角形。如果小于50，那么暴力排序扫一遍即可。所以最坏复杂度O(q*50*log50)然而我并没有这种脑洞- -！代码:;ll;int n,q,cnt;ll a[N];int head[N];int fa[N][22],deep[N];int tot;ll temp[N];struct node{int from,to,next;}edge[N];void init(){memset(head,-1,sizeof(head));cnt=1;}void edgeadd(int from,int to){edge[cnt].from=from,edge[cnt].to=to;edge[cnt].next=head[from];head[from]=cnt++;}void dfs(int now,int ff,int depth){fa[now][0]=ff,deep[now]=depth;for(int i=head[now];i!=-1;i=edge[i].next){int to=edge[i].to;dfs(to,now,depth+1);}}int lca(int x,int y){if(deep[x]<deep[y])swap(x,y);for(int i=20;i>=0;i–){if(deep[fa[x][i]]>=deep[y])x=fa[x][i];}if(x==y)return x;for(int i=20;i>=0;i–){if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];}return fa[x][0];}int check(){if(tot<3)return 0;for(int i=3;i<=tot;i++){if(temp[i-1]+temp[i-2]>temp[i])return 1;}return 0;}int main(){init();scanf(“%d%d”,&n,&q);for(int i=1;i<=n;i++)scanf(“%d”,&a[i]);for(int i=1;i<n;i++){int x,y;scanf(“%d%d”,&x,&y);edgeadd(x,y);}dfs(1,0,1);for(int i=1;i<=n;i++){for(int j=1;j<=20;j++){fa[i][j]=fa[fa[i][j-1]][j-1];}}for(int i=1;i<=q;i++){int opt,x,y;scanf(“%d%d%d”,&opt,&x,&y);if(opt==0){int tmp=lca(x,y);tot=0;int flag=0;while(x!=tmp){temp[++tot]=a[x],x=fa[x][0];if(tot>=50){flag=1;puts(“Y”);break;}}if(flag)continue;while(y!=tmp){temp[++tot]=a[y],y=fa[y][0];if(tot>=50){flag=1;puts(“Y”);break;}}if(flag)continue;temp[++tot]=a[tmp];if(tot>=50){puts(“Y”);continue;}sort(temp+1,temp+tot+1);if(check())puts(“Y”);else puts(“N”);}else{a[x]=y;}}}
喜欢就喜欢了，心被牵动，无须理由，爱上你是我的自由，
