5 52 54 21 31 45 1 5 12 2 1 44 1 3 43 1 1 53 5 1 4

YNYYY

/*  第一遍做是找出公共祖先，然后遍历路径，毫无疑问的TLE了，题解好棒  思路：设从A到B，经过的深度最小的点为X 同理，C,D的为Y  题目是一个点从A出发到B 一个从C出发到D  那么从A到B可以分解成 先从A到X 再从X到B。。。 C同理  假设能相遇 那么  要么在A到X的过程A,B相遇 要么在X到B的过程A,B相遇  对于在A到X的过程相遇的情况 又可以分解为：  情况1：  在A到X的过程和 C到Y的过程 中A,B相遇 此时相遇点的深度必然大于等于MIN（X深度，Y深度）  情况2：  在A到X的过程和 Y到D的过程 中A,B相遇 此时相遇点的深度必然大于等于MIN （X深度，Y深度）  另一种情况同理。。。  所以显然只要求出MIN=min(lca(a,b),lca(c,d));(lca返回的是两个点公共祖先的最大深度  假如lca(a,c) lca(a,d) lca(b,c) lca(b,d) 中有任意一个大于等于MIN 的话 那么可以相遇 否则不能 */#include<cstdio>#include<iostream>#include<cstring>#define N 100010using namespace std;int head[N],deep[N],vis[N],fa[N][25],n,m;struct node{    int v,pre;};node e[N*2];void add(int i,int x,int y){    e[i].v=y;    e[i].pre=head[x];    head[x]=i;}void dfs(int now,int from,int c){    fa[now][0]=from;deep[now]=c;    for(int i=head[now];i;i=e[i].pre)      if(e[i].v!=from)        dfs(e[i].v,now,c+1);}void get_fa(){    for(int j=1;j<=20;j++)      for(int i=1;i<=n;i++)        fa[i][j]=fa[fa[i][j-1]][j-1];}int get_same(int a,int t){    for(int i=0;i<=20;i++)      if((1<<i)&t)a=fa[a][i];    return a;}int LCA(int a,int b){    if(deep[a]<deep[b])swap(a,b);    a=get_same(a,deep[a]-deep[b]);    if(a==b)return deep[a];    for(int i=20;i>=0;i--)      if(fa[a][i]!=fa[b][i])      {          a=fa[a][i];          b=fa[b][i];      }    return deep[fa[a][0]];}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<n;i++)    {        int x,y;        scanf("%d%d",&x,&y);        add(i*2-1,x,y);add(i*2,y,x);    }    dfs(1,1,0);get_fa();    for(int i=1;i<=m;i++)    {        int s1,t1,s2,t2;        scanf("%d%d%d%d",&s1,&t1,&s2,&t2);        int MAX=max(LCA(s1,t1),LCA(s2,t2));        if(LCA(s1,t2)>=MAX||LCA(s2,t1)>=MAX||LCA(s1,s2)>=MAX||LCA(t1,t2)>=MAX)          printf("Y\n");        else printf("N\n");    }    return 0;}