又是没想出来的 trick。
思路
考虑两条路径相交时的情况。
这种情况一定是不存在的，因为中间的交叉点往上出现了两条分支，而树上每个节点只有一个父节点。所以交叉点一定是其中一条路径深度最小的点，即某一组的最近公共祖先。
那么两条路径相交，当且仅当其中一条路径对应两点的 LCA 在另一条路径上。
接下来只需要考虑怎么判断一个点是否在一条路径上。无权树上又有一个性质，即在两点路径外的点到两点的距离和一定大于两点的距离。所以判断一个点是否在一条路径上，只需要看其到两端点的距离和是否等于两端点的距离。
用 LCA 和深度差，分别求出两组的 LCA 到另一组两点的距离和，任意一组满足条件即相交。
实现
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int n,q,D;
int h[N],tot;
int dep[N],fa[N][20];
struct Node{int to,nxt;
}e[2*N];
void Add(int u,int v){tot++;e[tot].to=v;e[tot].nxt=h[u];h[u]=tot;
}
void dfs(int u,int cur,int fath){dep[u]=cur;D=max(D,cur);fa[u][0]=fath;for(int i=1;i<=log(dep[u])/log(2);i++) fa[u][i]=fa[fa[u][i-1]][i-1];for(int i=h[u];i;i=e[i].nxt){int v=e[i].to;if(v!=fath) dfs(v,cur+1,u);}
}
int LCA(int a,int b){if(dep[a]<dep[b]) swap(a,b);for(int i=log(D)/log(2);i>=0;i--){if(dep[fa[a][i]]>=dep[b]) a=fa[a][i];}if(a==b) return a;for(int i=log(D)/log(2);i>=0;i--){if(fa[a][i]!=fa[b][i]) a=fa[a][i],b=fa[b][i];}return fa[a][0];
}
int Abs(int x){if(x<0) return -x;else return x;
}
int dis(int a,int b){int fab=LCA(a,b);return Abs(dep[a]-dep[fab])+Abs(dep[b]-dep[fab]);
}
int main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);cin>>n>>q;for(int i=1;i<=n-1;i++){int u,v;cin>>u>>v;Add(u,v),Add(v,u);}dfs(1,1,0);for(int i=1;i<=q;i++){int a,b,c,d;cin>>a>>b>>c>>d;int fab,fcd;fab=LCA(a,b),fcd=LCA(c,d);if(dis(fab,c)+dis(fab,d)==dis(c,d)||dis(fcd,a)+dis(fcd,b)==dis(a,b)) cout<<"Y\n";else cout<<"N\n";}return 0;
}