Luogu | P3398 仓鼠找 Sugar | 图论 | LCA


Description

小仓鼠的和他的基友 sugar 住在地下洞穴中,每个节点的编号为 $1\sim n$。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室(a)到餐厅(b),而他的基友同时要从他的卧室(c)到图书馆(d)。他们都会走最短路径。现在小仓鼠希望知道,有没有可能在某个地方,可以碰到他的基友?

小仓鼠那么弱,还要天天被 zzq 大爷虐,请你快来救救他吧!


Input Format

第一行两个正整数 $n$ 和 $q$ ,表示这棵树节点的个数和询问的个数。

接下来 $n-1$ 行,每行两个正整数 $u$ 和 $v$ ,表示节点 $u$ 到节点 $v$ 之间有一条边。

接下来 $q$ 行,每行四个正整数 $a、b、c$ 和 $d$ ,表示节点编号,也就是一次询问,其意义如上。


Output Format

对于每个询问,如果有公共点,输出大写字母 Y ;否则输出 N


Input Sample

Sample 01

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


Output Sample

Sample 01

Y
N
Y
Y
Y


Data Range

$1 \le n,q \le 10^5$。


Solution

有一个很神奇的性质:若 $a、b$ 与 $c、d$ 相交,则至少有一方的 LCA 在另一方的路径上。

具体实现时判断 LCA 到两个端点的距离之和若等于两个端点的距离,则 LCA 在路径上。


Code

#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

inline void Read(int &x){
    x=0; char ch=0; while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar(); return;
}

struct edge{
    int from;
    int to;
    int next;
}e[200005];

int N;
int Q;
int node;

int first[100005];
int last[100005];
int size[100005];
int hvs[100005];
int dep[100005]; 
int top[100005];
int fa[100005];

void addedge(int u,int v){
    e[++node]=(edge){u,v,0};
    if(first[u]==0) first[u]=node;
    else e[last[u]].next=node;
    last[u]=node; return;
}

void DFS1(int x){
    size[x]=1;
    dep[x]=dep[fa[x]]+1;
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to;
        if(y==fa[x])
            continue;
        fa[y]=x;
        DFS1(y);
        size[x]+=size[y];
        if(size[hvs[x]]<size[y])
            hvs[x]=y;
    }
    return;
}

void DFS2(int x,int head){
    top[x]=head;
    if(hvs[x])
        DFS2(hvs[x],head);
    for(int p=first[x];p;p=e[p].next){
        int y=e[p].to;
        if(y==fa[x]||y==hvs[x])
            continue;
        DFS2(y,y);
    }
    return;
}

int LCA(int x,int y){
    while(top[x]!=top[y]){
        if(dep[top[x]]<dep[top[y]])
            swap(x,y);
        x=fa[top[x]];
    }
    return dep[x]<dep[y]?x:y;
}

int dist(int x,int y){
    return dep[x]+dep[y]-2*dep[LCA(x,y)];
}

bool judge(int f,int t,int x,int y){
    int LCA1=LCA(f,t);
    if(dist(x,y)==dist(LCA1,x)+dist(LCA1,y))
        return 1;
    int LCA2=LCA(x,y);
    if(dist(f,t)==dist(LCA2,f)+dist(LCA2,t))
        return 1;
    return 0;
}

int main(){
    int f,t,x,y;
    Read(N);
    Read(Q);
    rep(i,2,N){
        Read(f);
        Read(t);
        addedge(f,t);
        addedge(t,f);
    }
    DFS1(1);
    DFS2(1,1);
    rep(i,1,Q){
        Read(f);
        Read(t);
        Read(x);
        Read(y);
        printf("%c\n","NY"[judge(f,t,x,y)]);
    }
    return 0;
}