题目描述

小仓鼠的和他的基\(（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在另一条路径上

而判断一个节点\(x\)，是否在路径\(a\)-\(b\)上需要满足如下几个条件

    - d[x]>=d[LCA(a,b)]

    - LCA(a,x)=x或LCA(b,x)=x;

其中d数组代表深度。

所以分两种情况讨论一下即可

时间复杂度\(O(n log n)\)，下面是树剖求\(LCA\)的代码，倍增照样可以做，就是慢了点。

代码：

#include<cstdio>
#include<algorithm>
#include<cctype>
#define maxn 100007
using namespace std;
int num,head[maxn],n,d[maxn],son[maxn],top[maxn],siz[maxn];
int cnt,id[maxn],fa[maxn],m;
inline int qread() {
  char c=getchar();int num=0,f=1;
  for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
  for(;isdigit(c);c=getchar()) num=num*10+c-'0';
  return num*f;
}
struct node {
  int v,nxt;
}e[maxn<<1];
inline void ct(int u, int v) {
  e[++num].v=v;
  e[num].nxt=head[u];
  head[u]=num;
}
void dfs1(int u) {
  siz[u]=1;
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(v!=fa[u]) {
      d[v]=d[u]+1;
      fa[v]=u;
      dfs1(v);
      siz[u]+=siz[v];
      if(siz[v]>siz[son[u]]) son[u]=v;
    }
  }
}
void dfs2(int u, int t) {
  id[u]=++cnt;
  top[u]=t;
  if(son[u]) dfs2(son[u],t);
  for(int i=head[u];i;i=e[i].nxt) {
    int v=e[i].v;
    if(v!=fa[u]&&v!=son[u]) dfs2(v,v);
  }
}
inline int lca(int x, int y) {
  int fx=top[x],fy=top[y];
  while(fx!=fy) {
    if(d[fx]<d[fy]) swap(x,y),swap(fx,fy);
    x=fa[fx],fx=top[x];
  }
  return d[x]>d[y]?y:x;
}
int main() {
  n=qread(),m=qread();
  for(int i=1,u,v;i<n;++i) {
    u=qread(),v=qread();
    ct(u,v),ct(v,u);
  }
  dfs1(1);dfs2(1,1);
  for(int i=1,a,b,c,p;i<=m;++i) {
    a=qread(),b=qread(),c=qread(),p=qread();
    int zrj=lca(a,b),cyh=lca(c,p);
    if(d[zrj]<d[cyh]) swap(zrj,cyh),swap(a,c),swap(b,p);
    if(lca(zrj,c)==zrj||lca(zrj,p)==zrj) printf("Y\n");
    else printf("N\n");
  }
  return 0;
}