题目描述
小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？

小仓鼠那么弱，还要天天被zzq大爷虐，请你快来救救他吧！

输入格式
第一行两个正整数n和q，表示这棵树节点的个数和询问的个数。

接下来n-1行，每行两个正整数u和v，表示节点u到节点v之间有一条边。

接下来q行，每行四个正整数a、b、c和d，表示节点编号，也就是一次询问，其意义如上。

输出格式
对于每个询问，如果有公共点，输出大写字母“Y”；否则输出“N”。

输入输出样例
输入 #1 复制
5 5
2 5
4 2
1 3
1 4
5 1 5 1
2 2 1 4
4 1 3 4
3 1 1 5
3 5 1 4
输出 #1 复制
Y
N
Y
Y
Y
说明/提示
本题时限1s，内存限制128M，因新评测机速度较为接近NOIP评测机速度，请注意常数问题带来的影响。

20%的数据 n<=200,q<=200

40%的数据 n<=2000,q<=2000

70%的数据 n<=50000,q<=50000

100%的数据 n<=100000,q<=100000

LCA解树上路径交和树上两点间距离

树上怎么求路径交呢？（这个就是题意所求），简单画图可知，如果树上两条路径会相交，那么设这两条路径为（a，b）与（c，d），x = lca（a，b），y = lca（c，d），则必有x在（c，d）路径上，或者 y在（a，b）路径上。

怎么求一个点是否在某条路径上呢？其实也很简单，如果这个点到路径两个端点的距离等于路径长度，那么就在这条路径上。

然后为了加快程序运行速度，我预处理了log2（i）+ 1 的值。

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,q,h[N],f[N][30],lg[N],d[N];
int head[N],nex[N<<1],to[N<<1],tot;
inline void add(int a,int b){
	to[++tot]=b; nex[tot]=head[a]; head[a]=tot;
}
void dfs(int x,int fa){
	h[x]=h[fa]+1;	f[x][0]=fa;
	for(int i=1;(1<<i)<=h[x];i++)	f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nex[i]){
		if(to[i]!=fa)	d[to[i]]=d[x]+1,dfs(to[i],x);
	}
}
inline int lca(int x,int y){
	if(h[x]<h[y])	swap(x,y);
	while(h[x]>h[y])	x=f[x][lg[h[x]-h[y]]-1];
	if(x==y)	return x;
	for(int i=lg[h[x]]-1;i>=0;i--)
		if(f[x][i]!=f[y][i])
			x=f[x][i],y=f[y][i];
	return f[x][0];
}
inline int dis(int a,int b){
	return d[a]+d[b]-2*d[lca(a,b)];
}
signed main(){
	scanf("%d %d",&n,&q);
	for(int i=1;i<n;i++){
		int a,b;	scanf("%d %d",&a,&b);	add(a,b);	add(b,a);
	}
	for(int i=1;i<=n;i++)	lg[i]=lg[i-1]+(1<<lg[i-1]==i);
	dfs(1,0);
	while(q--){
		int a,b,c,d;	scanf("%d %d %d %d",&a,&b,&c,&d);
		int x=lca(a,b);	int y=lca(c,d);
		if(dis(c,d)==dis(x,c)+dis(x,d)||dis(a,b)==dis(y,a)+dis(y,b))	puts("Y");
		else	puts("N");
	}
	return 0;
}