比赛 |
“Asm.Def战记之夏威夷”杯 |
评测结果 |
WWAWWWWWWW |
题目名称 |
Asm.Def的病毒 |
最终得分 |
10 |
用户昵称 |
lxtgogogo |
运行时间 |
0.017 s |
代码语言 |
C++ |
内存使用 |
1.30 MiB |
提交时间 |
2015-11-06 09:39:38 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<iomanip>
#include<cstring>
#include<queue>
#include<ctime>
#include<cstdlib>
using namespace std;
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-'0';ch=getchar();}
return x*f;
}
int n=0,t=0;
bool a[1010][1010]={},f[1010]={};
int ceng[1010]={};
int father[1010]={};
int q[1010]={},head=0,tail=0;
void init(){
n=read();t=read();
int x=0,y=0;
for(int i=1;i<n;i++) {x=read();y=read();a[x][y]=1;a[y][x]=1;}
for(int i=1;i<=n;i++) father[i]=i;
q[++tail]=1;
ceng[1]=1;
father[1]=0;
for(head=1;head<=tail;head++)
{
int x=q[head];
for(int i=1;i<=n;i++)
if(a[x][i] && father[i]==i)
{
father[i]=x;
ceng[i]=ceng[x]+1;
q[++tail]=i;
}
}
}
void work(){
int a=0,b=0;
while(t--)
{
memset(f,0,sizeof(f));
a=read();b=read();
f[a]=true;f[b]=true;
int c=max(ceng[a],ceng[b]);
int fa=father[a],fb=father[b];
while(c--)
{
if(fa==fb) {f[fa]=true;break;}
f[fa]=true;f[fb]=true;
if(ceng[fa]==c) fa=father[fa];
if(ceng[fb]==c) fb=father[fb];
}
a=read();b=read();
bool flag=false;
if(f[a] || f[b]) flag=true;
c=max(ceng[a],ceng[b]);
fa=father[a];fb=father[b];
while(c--)
{
if(f[fa] || f[fb]) {flag=true;break;}
if(fa==fb) {break;}
if(ceng[fa]==c) fa=father[fa];
if(ceng[fb]==c) fb=father[fb];
}
if(flag) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
int main(){
freopen("asm_virus.in","r",stdin);
freopen("asm_virus.out","w",stdout);
init();
work();
fclose(stdin);fclose(stdout);
return 0;
}