提交记录

#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+10;
int n,m,s;
int h[mx],st[mx][24];
vector<int> tree[mx];
void dfsh(int n,int fa){
  h[n]=h[fa]+1,st[n][0]=fa;
  for(int i=0;i<tree[n].size();i++){
    if(tree[n][i]!=fa) dfsh(tree[n][i],n);
  }
}
int lca(int u,int v){//u>=v
  if(h[u]>h[v]) swap(u,v);
  int cz=h[v]-h[u];
  for(int i=0;(1<<i)<=cz;i++){
    if((cz>>i)&1){
      v=st[v][i];cz^=(1<<i);
    }
  }
  //printf("u%d v%d ",u,v);
  if(u==v) return u;
  for(int i=18;i>=0;i--){ 
    if(st[u][i]==st[v][i]) continue;
    u=st[u][i];v=st[v][i];
    //printf("u%d v%d ",u,v);
  }
  return st[u][0];
}
int main(){
  scanf("%d%d%d",&n,&m);
  for(int i=1;i<n;i++){
    int x,y;
    scanf("%d%d",&x,&y);
    tree[x].push_back(y);tree[y].push_back(x);
  }
  h[0]=0,dfsh(1,0);
  for(int i=1;(1<<i)<=n;i++){
    for(int j=1;j<=n;j++){
      st[j][i]=st[st[j][i-1]][i-1];
    }
  }
  while(m--){
    int a,b,c,d;
    scanf("%d%d%d%d",&a,&b,&c,&d);
    int l1=lca(a,b),l2=lca(c,d);
    int l3=lca(l1,l2);
    if(l1==l2||l3==l1||l3==l2) printf("Y\n");
    else printf("N\n");
  }
  return 0;
}