比赛 “Asm.Def战记之夏威夷”杯 评测结果 AAAAAAAAAA
题目名称 Asm.Def的病毒 最终得分 100
用户昵称 Satoshi 运行时间 0.338 s
代码语言 C++ 内存使用 0.33 MiB
提交时间 2015-11-06 09:17:54
显示代码纯文本
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#define N 1010
using namespace std;
ifstream in("asm_virus.in");
ofstream out("asm_virus.out");
int n,Q;
vector<int> G[N];
int p[N]={0};
bool l[N]={0},vis1[N]={0},vis2[N]={0};
void read()
{
	int i,u,v;
	in>>n>>Q;
	for(i=1;i<n;i++)
	{
		in>>u>>v;
		G[u].push_back(v);
		G[v].push_back(u);
	}
}
void BFS(int s)
{
	int i,u,v;
	queue<int> q;
	for(i=1;i<=n;i++)
	{
		l[i]=0;
		p[i]=i;
	}
	q.push(s);
	while(!q.empty())
	{
		u=q.front();
		q.pop();
		l[u]=1;
		for(i=0;i<G[u].size();i++)
		{
			v=G[u][i];
			if(!l[v])
			{
				p[v]=u;
				q.push(v);
			}
		}
	}
}
void update1(int x,int y)
{
	int i;
	while(true)
	{
		vis1[y]=1;
		if(y==x)break;
		y=p[y];
	}
}
void update2(int x,int y)
{
	while(true)
	{
		vis2[y]=1;
		if(y==x)break;
		y=p[y];
	}
}
bool check()
{
	int i;
	for(i=1;i<=n;i++)if(vis1[i]&&vis2[i])return 1;
	return 0;
}
void work()
{
	int i,j,s1,t1,s2,t2;
	for(i=1;i<=Q;i++)
	{
		for(j=1;j<=n;j++)vis1[j]=vis2[j]=0;
		in>>s1>>t1>>s2>>t2;
		BFS(s1);
		update1(s1,t1);
		BFS(s2);
		update2(s2,t2);
		if(check())out<<"YES"<<endl;
		else out<<"NO"<<endl;
	}
}
int main()
{
	read();
	work();
	return 0;
}