P3398 仓鼠找sugar

题面:https://www.luogu.org/problem/P3398

本题有个很好的方法:显然当lca(a,b)在c,d路径上出现过,或者lca(c,d)在a,b路径上出现过,那么这两条路径一定重合.
(注:一个点在路径上当且仅当这个点到这条路径两端点距离和等于这条路径长度.)
Code:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<ctime>
using namespace std;
const int N=500005;
int n,m,s,head[N],cnt,fa[N],anc[N][25],dep[N];
struct Node{
	int u,v,nxt;
}edge[N*2];
void add(int u,int v){
	++cnt;
	edge[cnt].u=u;
	edge[cnt].v=v;
	edge[cnt].nxt=head[u];
	head[u]=cnt;
}
void dfs(int u){
	anc[u][0]=fa[u];
	for(int i=1;i<=22;i++){
		anc[u][i]=anc[anc[u][i-1]][i-1];
	}
	for(int i=head[u];i;i=edge[i].nxt){
		int v=edge[i].v;
		if(v!=fa[u]){
			fa[v]=u;
			dep[v]=dep[u]+1;
			dfs(v);
		}
	}
}
int lca(int x,int y){
	if(dep[x]<dep[y]){
		swap(x,y);
	}
	for(int i=22;i>=0;i--){
		if(dep[anc[x][i]]>=dep[y]){
			x=anc[x][i];
		}
	}
	if(x==y){
		return x;
	}
	for(int i=22;i>=0;i--){
		if(anc[x][i]!=anc[y][i]){
			x=anc[x][i];
			y=anc[y][i];
		}
	}
	return anc[x][0];
}
int dis(int a,int b){
	return dep[a]+dep[b]-2*dep[lca(a,b)];
}
int main(){
	scanf("%d%d",&n,&m);
	s=1;
	for(int i=1;i<n;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		add(x,y);
		add(y,x);
	}
	dep[s]=1;
	dfs(s);
	for(int i=1;i<=m;i++){
		int a,b,c,d;
		scanf("%d%d%d%d",&a,&b,&c,&d);
		int p=lca(a,b);
		int q=lca(c,d);
		if(dis(c,p)+dis(d,p)==dis(c,d)||dis(a,q)+dis(b,q)==dis(a,b)){
			printf("Y\n");
		}
		else{
			printf("N\n");
		}
	}
	return 0;
}