#5 #8 #9 WA

LCA部分应该没有错，判断是否相交部分与题解3思路相同。

#include<bits/stdc++.h>
using namespace std;
int n,m,num;
int depth[500002],h[500002],power[500002],ancestors[500002][22];
struct tree{
	int to,next;
}e[1000000];
void cb(int from,int to){
	num++;
	e[num].to=to;
	e[num].next=h[from];
	h[from]=num;
}
void an(int u,int fa){
	depth[u]=depth[fa]+1;
	ancestors[u][0]=fa;
	for(int i=1;i<=power[depth[u]];i++)
		ancestors[u][i]=ancestors[ancestors[u][i-1]][i-1];
	for(int i=h[u];i;i=e[i].next)
		if(e[i].to!=fa)
			an(e[i].to,u);
}
int LCA(int x,int y){
	if(depth[x]<depth[y]){
		int u=x;
		x=y;
		y=u;
	}
	while(depth[x]>depth[y])
		x=ancestors[x][power[(depth[x]-depth[y])]-1];
	if(x==y)
		return y;
	for(int i=power[x]-1;i>=0;i--){
		if(ancestors[x][i]!=ancestors[y][i]){
			x=ancestors[x][i];
			y=ancestors[y][i];
		}
	}
	return ancestors[x][0];
} 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n-1;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		cb(x,y);
		cb(y,x);
	}
	for(int i=1;i<=n;i++)
		power[i]=power[i-1]+(1<<power[i-1]==i);
	an(1,0);
	for(int i=1;i<=m;i++){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		int x=LCA(a,b),y=LCA(c,d),l=max(depth[LCA(a,c)],max(depth[LCA(a,d)],max(depth[LCA(b,c)],depth[LCA(b,d)])));
		if(l>=depth[x]&&l>=depth[y])
			cout<<"Y"<<endl;
		else
			cout<<"N"<<endl;
	}
	return 0;
}