F.A.Qs Home ProblemSet Status Ranklist Contest LoginRegister
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
大视野在线测评-欢迎您
[ New Thread ]
Problem 3251 >> 哪位帮看一下为何wa
magician @ 2018-05-29 17:35:08
[ Quote ] [ Edit ] [ Delete ] 1#
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<cctype>
#include<cmath>
#include<cstdlib>
#include<ctime>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<stack>
using namespace std;
int fa[210000],d[210000],a[210000],dep[210000];
vector<int>v[210000];
void dfs(int x){
int i;
for(i=0;i<v[x].size();i++){
dep[v[x][i]]=dep[x]+1;
dfs(v[x][i]);
}
return;
}
int main(){
int n,m,i,j,k,x,y;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)scanf("%d",&d[i]);
for(i=1;i<n;i++){
scanf("%d%d",&x,&y);
fa[y]=x;
v[x].push_back(y);
}
dep[1]=1;
dfs(1);
for(i=1;i<=m;i++){
scanf("%d%d%d",&k,&x,&y);
if(k)d[x]=y;
else {
int cnt=0,ok=0;
if(n>=50)ok=1;
if(!ok){
if(dep[x]<dep[y])swap(x,y);
while(dep[x]>dep[y]){
a[++cnt]=d[x];
x=fa[x];
if(cnt>=50){ok=1;break;}
}
while(x!=y){
a[++cnt]=d[x];
a[++cnt]=d[y];
x=fa[x];
y=fa[y];
if(cnt>=50){ok=1;break;}
}
a[++cnt]=d[x];
if(cnt>=50)ok=1;
if(!ok){
sort(a+1,a+cnt+1);
for(j=1;j<cnt-1;j++)
if(1ll*(a[j]+a[j+1])>1ll*a[j+2]){
ok=1;
break;
}
}
}
if(!ok)printf("N\n");
else printf("Y\n");
}
}
return 0;
}
[Top] [Previous Page] [Next Page]

HOME Back