比赛 “Asm.Def战记之夏威夷”杯 评测结果 AAAAAAAAAA
题目名称 Asm.Def的病毒 最终得分 100
用户昵称 万千世界,吾为大主宰 运行时间 0.037 s
代码语言 C++ 内存使用 0.37 MiB
提交时间 2015-11-06 08:42:57
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<cstring>
#include<deque>
#include<map>
#define ll long long

using namespace std;
int be[1001],en[1001];
int n,q;
struct sd{
	int nex,to;
}e[10001];int h[1001],tot=0,no=0;
int fa[1001];
void add(int x,int y){tot++;e[tot].nex=h[x];e[tot].to=y;h[x]=tot;}
void dfs(int x,int faa)
{
	be[x]=++no;fa[x]=faa;
	for(int i=h[x];i;i=e[i].nex)
	{
		if(e[i].to!=faa)
		{
			dfs(e[i].to,x);
		}
	}
	en[x]=++no;
}
bool vis[1001],vis2[1001];
void find1(int x)
{
	vis[x]=1;
	if(x==1)return;
	find1(fa[x]);
}
bool u;
void find2(int x)
{
	if(!vis[x])vis[x]=1;
	else if(!u)u=1;
	else vis[x]=0;
	if(x==1)return;
	find2(fa[x]);
}
void find3(int x)
{
	vis2[x]=1;
	if(x==1)return;
	find3(fa[x]);
}
bool u2;
void find4(int x)
{
	if(!vis2[x])vis2[x]=1;
	else if(!u2)u2=1;
	else vis2[x]=0;
	if(x==1)return;
	find4(fa[x]);
}
int main()
{
	freopen("asm_virus.in","r",stdin);
	freopen("asm_virus.out","w",stdout);
	scanf("%d%d",&n,&q);
	int x,y,x2,y2;
	for(int i=1;i<n;i++)
	{
		scanf("%d%d",&x,&y);
		add(x,y);add(y,x);
	}
	dfs(1,0);
	for(int i=1;i<=q;i++)
	{
		scanf("%d%d%d%d",&x,&y,&x2,&y2);
		u=0;u2=0;
		memset(vis,0,sizeof vis);
		memset(vis2,0,sizeof vis2);
		find1(x);find2(y);
		find3(x2);find4(y2);
		bool p=0;
		for(int j=1;j<=n;j++)
		if(vis[j]&&vis2[j])
		{
			p=1;break;
		}
		if(p)printf("YES\n");
		else printf("NO\n");
	}
}