记录编号	206288	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm.Def的病毒	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2015-11-06 15:41:25	内存使用	0.68 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
using namespace std;
const int SIZEN=2010;//乘一波2
int N,Q;
vector<int> G[SIZEN];
int dfn[SIZEN],father[SIZEN];
int depth[SIZEN]={0};
int dfslis[2*SIZEN],dfslen=0;
int ST[2*SIZEN][20];
int log_2(int x){
	int ans=-1;
	while(x){
		ans++;
		x>>=1;
	}
	return ans;
}
int LCA(int a,int b){
	int l=dfn[a],r=dfn[b];
	if(l>r) swap(l,r);
	int m=log_2(r-l+1);
	int x=ST[l][m],y=ST[r-(1<<m)+1][m];
	return depth[x]<depth[y]?x:y;
}
void ST_prepare(void){
	for(int i=1;i<=dfslen;i++) ST[i][0]=dfslis[i];
	int m=log_2(dfslen);
	for(int j=1;j<=m;j++){
		for(int i=1;i<=dfslen;i++){
			int x=ST[i][j-1],y=ST[i+(1<<j-1)][j-1];
			ST[i][j]=depth[x]<depth[y]?x:y;
		}
	}
}
void DFS(int x){
	dfslen++;
	dfslis[dfslen]=x,dfn[x]=dfslen;
	for(int i=0;i<G[x].size();i++){
		int u=G[x][i];
		if(u==father[x]) continue;
		father[u]=x;
		depth[u]=depth[x]+1;
		DFS(u);
		dfslis[++dfslen]=x;
	}
}
void read(void){
	scanf("%d%d",&N,&Q);
	int x,y;
	for(int i=1;i<N;i++){
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
}
bool is_on(int p,int anc,int x){//p是否在anc~x路径上,anc是x的祖先
	return LCA(p,anc)==anc&&LCA(x,p)==p;
}
bool is_cross(int s1,int t1,int s2,int t2){
	int g1=LCA(s1,t1),g2=LCA(s2,t2);
	if(is_on(g1,g2,s2)||is_on(g1,g2,t2)) return true;//g1在s2~t2路径上
	if(is_on(s1,g2,s2)||is_on(s1,g2,t2)) return true;//g1在s2~t2路径上
	if(is_on(t1,g2,s2)||is_on(t1,g2,t2)) return true;//g1在s2~t2路径上
	if(is_on(g2,g1,s1)||is_on(g2,g1,t1)) return true;//g2在s1~t1路径上
	if(is_on(s2,g1,s1)||is_on(s2,g1,t1)) return true;//g2在s1~t1路径上
	if(is_on(t2,g1,s1)||is_on(t2,g1,t1)) return true;//g2在s1~t1路径上
	return false;
}
void work(void){
	int s1,t1,s2,t2;
	for(int i=1;i<=Q;i++){
		scanf("%d%d%d%d",&s1,&t1,&s2,&t2);
		if(is_cross(s1,t1,s2,t2)) printf("YES\n");
		else printf("NO\n");
	}
}
int main(){
	freopen("asm_virus.in","r",stdin);
	freopen("asm_virus.out","w",stdout);
	read();
	depth[1]=1;//注意,0的深度为0
	DFS(1);
	ST_prepare();
	work();
	return 0;
}