比赛 “Asm.Def战记之夏威夷”杯 评测结果 WWWWWWWWWW
题目名称 Asm.Def的病毒 最终得分 0
用户昵称 咸鱼二号 运行时间 0.025 s
代码语言 C++ 内存使用 0.31 MiB
提交时间 2015-11-06 09:05:28
显示代码纯文本
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<utility>
#include<stdio.h>
#include<cstdlib>
#include<iomanip>	//cout<<setiosflags(ios::fixed)<<setprecision(2);
#include<ctime> //double a=(double)clock();	cout<<a<<endl;
#include<vector>
#include<queue>
using namespace std;
inline int read()
{
	int x=0,ff=1;char ch=getchar();
	while(ch>'9'||ch<'0'){if(ch=='-')ff=-1;ch=getchar();}
	while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=getchar();}
	return ff*x;
}
int N,Q,t1,t2;
int lin[1010],len=0;
struct edge
{
	int y,next;
}e[2010];
inline void insert(int xx,int yy)
{
	e[++len].next=lin[xx];
	lin[xx]=len;
	e[len].y=yy;
}
int q[1010],head,tail,depth[1010],prev[1010];
bool vis[1010];
void bfs()
{
	head=tail=0;
	q[head]=1,depth[1]=1;
	for(;head<=tail;head++)
	{
		for(int i=lin[q[head]];i;i=e[i].next)
		{
			if(!depth[e[i].y])
			{
				prev[e[i].y]=q[head];
				depth[e[i].y]=depth[q[head]]+1;
				q[++tail]=e[i].y;
			}
		}
	}
}
void cross1(int a,int b)
{
	memset(vis,0,sizeof(vis));
	if(depth[a]<depth[b])
		swap(a,b);
	while(depth[a]!=depth[b])
	{
		vis[a]=1;
		a=prev[a];
	}
	if(a==b)
		return;
	while(a!=b)
	{
		vis[a]=1,vis[b]=1;
		a=prev[a],b=prev[b];
	}
}
bool cross2(int a,int b)
{
	if(depth[a]<depth[b])
		swap(a,b);
	while(depth[a]!=depth[b])
	{
		if(vis[a])
			return 1;
		a=prev[a];
	}
	if(a==b)
		return 0;
	while(a!=b)
	{
		if(vis[a]||vis[b])
			return 1;
		a=prev[a],b=prev[b];
	}
	return 0;
}
int main()
{
	freopen("asm_virus.in","r",stdin);
	freopen("asm_virus.out","w",stdout);
	N=read(),Q=read();
	for(int i=1;i<N;i++)
	{
		t1=read(),t2=read();
		insert(t1,t2),insert(t2,t1);
	}
	bfs();
	for(int i=1;i<=Q;i++)
	{
		t1=read(),t2=read();
		cross1(t1,t2);
		t1=read(),t2=read();
		if(cross2(t1,t2))
			printf("YES\n");
		else
			printf("NO\n");
	}
	fclose(stdin),fclose(stdout);
	return 0;
}