比赛 “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;
}