记录编号	335474	评测结果	AAAAAAAAAA
题目名称	[HZOI 2016]非触	最终得分	100
用户昵称	rewine	是否通过	通过
代码语言	C++	运行时间	3.736 s
提交时间	2016-11-02 12:06:39	内存使用	57.54 MiB

#include<cmath>
#include<cstring>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<iostream>
#define Begin freopen("cp.in","r",stdin);freopen("cp.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
using namespace std;
const int maxn=1000010;
struct Edge{
    int next,to;
}e[maxn<<2];
int n,m,son[maxn],deep[maxn],size[maxn],root[maxn],top[maxn];
int len,head[maxn],id[maxn],cnt;
void Init();
void Insert(int x,int y){
    len++;e[len].to=y;e[len].next=head[x];head[x]=len;
}
void Dfs1(int x) {
    size[x]=1;son[x]=0;
    for(int i=head[x];i;i=e[i].next){
        int j=e[i].to;
        if(root[x]!=j){
            root[j]=x;deep[j]=deep[x]+1;
            Dfs1(j);
            size[x]+=size[j];
            if(size[son[x]]<size[j])son[x]=j; 
        }
    }
} 
void Dfs2(int x,int tp){
    top[x]=tp;id[x]=++cnt;
    if(son[x])Dfs2(son[x],tp);
    for(int i=head[x];i;i=e[i].next){
        int j=e[i].to;
        if(root[x]!=j && son[x]!=j)Dfs2(j,j);
    }
}
int Lca(int x,int y) {
    int fx=top[x],fy=top[y];
    while(fx!=fy){
        if(deep[fx]<deep[fy]){swap(fx,fy);swap(x,y);}
        x=root[fx];fx=top[x];
    }
    if(deep[x]>deep[y])swap(x,y);
    return x;
}
bool Judge(int x,int y,int lca) {
    int fx=top[x],fy=top[y];
    while(fx!=fy) {
        if(deep[fx]<deep[fy]){swap(fx,fy);swap(x,y);}
        if(id[lca]>=id[fx] && id[lca]<=id[x])return true;
        x=root[fx];fx=top[x];
    }
    if(deep[x]>deep[y])swap(x,y);
    if(id[lca]>=id[x] && id[lca]<=id[y])return true;
    return false;
}
int main(){
    Begin;
    int __size__=128<<20;
    char *__p__=(char*)malloc(__size__)+__size__;
    __asm__("movl %0, %%esp\n"::"r"(__p__));
    Init();
    //system("pause");
    End;
    return 0;
}
void Init(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<n;i++){
        int x,y;scanf("%d%d",&x,&y);
        Insert(x,y);Insert(y,x);
    }
    deep[1]=1;Dfs1(1);Dfs2(1,1);
    for(int i=1;i<=m;i++){
        int s,t,l,r;
        scanf("%d%d%d%d",&s,&t,&l,&r);
        int x=Lca(s,t);
        if(Judge(l,r,x)){printf("YES\n");continue;}
        x=Lca(l,r);
        if(Judge(s,t,x)){printf("YES\n");continue;}
        printf("NO\n");
    } 
}