比赛 “Asm.Def战记之夏威夷”杯 评测结果 WWWWWWWWWA
题目名称 Asm.Def的病毒 最终得分 10
用户昵称 sxysxy 运行时间 0.120 s
代码语言 C++ 内存使用 0.33 MiB
提交时间 2015-11-06 09:40:10
显示代码纯文本
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <queue>
using namespace std;
//#define dbg

#ifndef dbg
void set_file()
{
	freopen("asm_virus.in", "r", stdin);
	freopen("asm_virus.out", "w", stdout);
}
#endif

int N;
int Q;
int s,t;
bool xxx;
bool y;

#define MAXN (1001)

vector<int> adj[MAXN];

void rd()
{
	int i;
	int u,v;
	scanf("%d %d", &N, &Q);
	for(i = 1; i <= N-1; i++)
	{
		scanf("%d %d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
}

int d[MAXN];
bool vs1[MAXN];
int p1[MAXN];

void bfs1(int s, int t)
{
	int u,v,i;
	queue<int> q;
	memset(vs1, false, sizeof(vs1));
	memset(p1, 0, sizeof(p1));
	
	//开启spfa
	for(i = 1; i <= N; i++)
	{
		d[i] = 0x7fffffff;
		vs1[i] = false;
	}
	q.push(s);
	vs1[s] = true;
	while(!q.empty())
	{
		u = q.front();
		q.pop();
		for(i = 0; i < adj[u].size(); i++)
		{
			v = adj[u][i];
			if(d[v] > d[u]+1)
			{
				d[v] = d[u]+1;
				p1[v] = u;
				if(!vs1[v])
				{
					q.push(v);
					vs1[v] = true;
				}
			}
		}
		vs1[u] = false;
	}
}

bool vs2[MAXN];
int p2[MAXN];

void bfs2(int s, int t)
{
	int u,v,i;
	queue<int> q;
	memset(vs2, false, sizeof(vs2));
	memset(p2, 0, sizeof(p2));
	
	//开启spfa
	for(i = 1; i <= N; i++)
	{
		d[i] = 0x7fffffff;
		vs2[i] = false;
	}
	q.push(s);
	vs2[s] = true;
	while(!q.empty())
	{
		u = q.front();
		q.pop();
		for(i = 0; i < adj[u].size(); i++)
		{
			v = adj[u][i];
			if(d[v] > d[u]+1)
			{
				d[v] = d[u]+1;
				p2[v] = u;
				if(!vs2[v])
				{
					q.push(v);
					vs2[v] = true;
				}
			}
		}
		vs2[u] = false;
	}
}


bool nt[MAXN];
void judge(int s1, int t1, int s2, int t2)
{
	memset(nt, false, sizeof(nt));
	int p,q;
	p = t1;
	q = t2;
	vector<int> l1;
	vector<int> l2;
	while(p != s1)
	{
		l1.push_back(p);
		p = p1[p];
	}
	while(q != s2)
	{
		l2.push_back(q);
		q = p2[q];
	}
	
	for(p = 0; p < l1.size(); p++)
	{
		for(q = 0; q < l2.size(); q++)
		{
			if(l1[p] == l2[q])
			{
				xxx = true;	
				goto ok;
			}
		}
	}
	ok:;
}

void solve()
{
	int s1,t1,s2,t2;
	int i;
	for(i = 1; i <= Q; i++)
	{
		scanf("%d %d %d %d", &s1, &t1, &s2, &t2);
		bfs1(s1, t1);
		bfs2(s2, t2);
		xxx = false;
		judge(s1, t1, s2, t2);
		
		if(xxx)
			printf("YES\n");
		else
			printf("NO\n"); 
	}
}

int main()
{
#ifndef dbg
	set_file();
#endif
	
	rd();
	solve();
	
	return 0;
}