记录编号	289406	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的病毒	最终得分	100
用户昵称	AntiLeaf	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2016-08-04 19:45:12	内存使用	0.32 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=1010;
struct edge{
	int to;
	edge *prev;
	edge():to(0),prev(NULL){}
}ee[maxn<<1];
void insert(int,int);
void dfs(int);
int LCA(int,int);
bool query(int,int,int);
int len=0;
edge *last[maxn]={NULL};
int n,m,prt[maxn]={0};
int x,y,z,w,a,b;
bool vis[maxn];
int main(){
#define MINE
#ifdef MINE
	freopen("asm_virus.in","r",stdin);
	freopen("asm_virus.out","w",stdout);
#endif
	/*int __size__=128<<20;
	char *__p__=(char*)malloc(__size__)+__size__;
	__asm__("movl %0, %%esp\n"::"r"(__p__));*/
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		insert(x,y);
		insert(y,x);
	}
	dfs(1);
	//for(int i=1;i<=n;i++)printf("prt[%d]=%d\n",i,prt[i]);
	while(m--){
		scanf("%d%d%d%d",&x,&y,&z,&w);
		a=LCA(x,y);
		b=LCA(z,w);
		if(query(a,z,w)||query(b,x,y))printf("YES\n");
		else printf("NO\n");
	}
	return 0;
}
void insert(int x,int y){
	ee[len].to=y;
	ee[len].prev=last[x];
	last[x]=&ee[len++];
}
void dfs(int x){
	int y;
	for(edge *e=last[x];e;e=e->prev){
		y=e->to;
		if(y==prt[x])continue;
		prt[y]=x;
		dfs(y);
	}
}
int LCA(int x,int y){
	memset(vis,0,sizeof(vis));
	while(x){
		vis[x]=true;
		x=prt[x];
	}
	while(y){
		if(vis[y])return y;
		y=prt[y];
	}
	return x;
}
bool query(int z,int x,int y){
	int w=LCA(x,y);
	do{
		//printf("%d ",x);
		if(z==x)return true;
		if(x==w)break;
		x=prt[x];
	}while(x);
	while(y&&y!=w){
		//printf("%d ",y);
		if(z==y)return true;
		y=prt[y];
	}
	return false;
}