记录编号	289071	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的病毒	最终得分	100
用户昵称	Hzoi_	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2016-08-03 20:09:53	内存使用	0.33 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 dfs1(int);
void dfs2(int,int);
int LCA(int,int);
bool query(int,int,int);
int len=0;
edge *last[maxn]={NULL};
int n,m,prt[maxn]={0},size[maxn]={0},son[maxn]={0};
int top[maxn]={0},depth[maxn]={0},first[maxn]={0},tim=0;
int x,y,z,w,a,b;
int main(){
#define MINE
#ifdef MINE
	freopen("asm_virus.in","r",stdin);
	freopen("asm_virus.out","w",stdout);
#endif
	scanf("%d%d",&n,&m);
	for(int i=1;i<n;i++){
		scanf("%d%d",&x,&y);
		insert(x,y);
		insert(y,x);
	}
	depth[1]=1;
	dfs1(1);
	dfs2(1,1);
	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 dfs1(int x){
	int y;
	size[x]=1;
	for(edge *e=last[x];e;e=e->prev){
		y=e->to;
		if(y==prt[x])continue;
		prt[y]=x;
		depth[y]=depth[x]+1;
		dfs1(y);
		size[x]+=size[y];
		if(size[y]>size[son[x]])son[x]=y;
	}
}
void dfs2(int x,int tp){
	int y;
	first[x]=++tim;
	top[x]=tp;
	if(son[x])dfs2(son[x],tp);
	for(edge  *e=last[x];e;e=e->prev){
		y=e->to;
		if(y==prt[x]||y==son[x])continue;
		dfs2(y,y);
	}
}
int LCA(int x,int y){
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(depth[fx]<depth[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		x=prt[fx];
		fx=top[x];
	}
	if(depth[x]>depth[y])swap(x,y);
	return x;
}
bool query(int z,int x,int y){
	int fx=top[x],fy=top[y];
	while(fx!=fy){
		if(depth[fx]<depth[fy]){
			swap(fx,fy);
			swap(x,y);
		}
		if(first[z]>=first[fx]&&first[z]<=first[x])return true;
		x=prt[fx];
		fx=top[x];
	}
	if(depth[x]>depth[y])swap(x,y);
	if(first[z]>=first[x]&&first[z]<=first[y])return true;
	return false;
}