题目略。
LCA题。
当满足题目要求的路径存在交叠的时候，必有一对点的LCA（设为点A）在另一对点（设为B,C）构造的路径上。
我们可以通过LCA计算A到B,C的距离，进行验证。
卡了2h没过结果是因为LOG表的预处理没写我真是服了
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int N=100100;
int n,m,fa[N][20],dpt[N],LOG[N],head[N],tmp=0;
struct EDGE{int nxt,to;} edg[N<<1];
inline int read(){
int x=0;char ch=getchar();
while (ch<'0'||ch>'9') ch=getchar();
while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
return x;
}
inline void prepare_LOG(){
int cnt=0;LOG[1]=0;
for (int i=2;i<=n;++i){
cnt+=((1<<(cnt+1))==i);
LOG[i]=cnt;
}
}
inline void build_tree(int now,int pre){
dpt[now]=dpt[pre]+1;
fa[now][0]=pre;
for (int i=head[now];i;i=edg[i].nxt){
int v=edg[i].to;
if (v!=pre) build_tree(v,now);
}
}
inline void add_edge(int u,int v) {
edg[++tmp].nxt=head[u];
edg[tmp].to=v;
head[u]=tmp;
}
inline void find_father(int x){
for (int i=1;i<=LOG[dpt[x]];++i){
fa[x][i]=fa[fa[x][i-1]][i-1];
}
for (int i=head[x];i;i=edg[i].nxt){
int v=edg[i].to;
if (v!=fa[x][0]) find_father(v);
}
return;
}
inline int LCA(int x,int y){
if (dpt[x]<dpt[y]) swap(x,y);
while (dpt[x]>dpt[y]) x=fa[x][LOG[dpt[x]-dpt[y]]];
if (x==y) return x;
for (int i=LOG[dpt[x]];i>=0;--i){
if (fa[x][i]!=fa[y][i]) {x=fa[x][i];y=fa[y][i];}
}
return fa[x][0];
}
int main(){
int i,j;
memset(head,0,sizeof(head));
n=read();m=read();
for (i=1;i<n;++i) {
int u=read(),v=read();
add_edge(u,v);add_edge(v,u);
}
dpt[1]=1;
prepare_LOG();
build_tree(1,0);
find_father(1);
while (m--){
int a=read(),b=read(),c=read(),d=read();
int ast1=LCA(a,b),ast2=LCA(c,d),
ast3=LCA(ast1,c),ast4=LCA(ast1,d),
ast5=LCA(ast2,a),ast6=LCA(ast2,b);
int LEN1=abs(dpt[a]-dpt[ast1])+abs(dpt[b]-dpt[ast1])+1,
LEN2=abs(dpt[c]-dpt[ast2])+abs(dpt[d]-dpt[ast2])+1;
int len1=abs(dpt[a]-dpt[ast5])+abs(dpt[ast2]-dpt[ast5])+abs(dpt[ast2]-dpt[ast6])+abs(dpt[b]-dpt[ast6])+1,
len2=abs(dpt[c]-dpt[ast3])+abs(dpt[ast1]-dpt[ast3])+abs(dpt[ast1]-dpt[ast4])+abs(dpt[d]-dpt[ast4])+1;
// printf("ast1=%d(ast3:%d,ast4:%d) ast2=%d(ast5:%d,ast6:%d)
LEN1=%d LEN2=%d len1=%d len2=%d
",ast1,ast3,ast4,ast2,ast5,ast6,LEN1,LEN2,len1,len2);
if ((LEN1==len1)||(LEN2==len2)) puts("Y");else puts("N");
}
return 0;
}