仓鼠找sugar

传送门

很有意思的LCA题。

因为这是一棵树，所以树上两条路径有交点的话，一定会满足其中一条路径的LCA在另一条路径上。这个是为什么呢？因为如果一条路径的LCA不在另一条路径上的话，那么其必然没有重合的路径，否则它就不是一棵树了（这样的话相当于路径出现交叉，但是树上只有一条路）

所以我们只需要求出给定两条路径的LCA，然后判断是否合法即可（取一条路径的LCA和另一条的端点判LCA是否是第一条路径的LCA即可）

用的是树剖求LCA。看一下代码。

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')

using namespace std;
typedef long long ll;
const int M = 100005;
const int INF = 1000000009;

int read()
{
    int ans = 0,op = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
    if(ch == '-') op = -1;
    ch = getchar();
    }
    while(ch >= '0' && ch <= '9')
    {
    ans *= 10;
    ans += ch - '0';
    ch = getchar();
    }
    return ans * op;
}

struct edge
{
    int to,next;
}e[M<<1];

int n,q,dep[M],size[M],hson[M],top[M],head[M],ecnt,x,y,a,b,c,d,fa[M],dfn[M],idx;

void add(int x,int y)
{
    e[++ecnt].to = y;
    e[ecnt].next = head[x];
    head[x] = ecnt;
}

void dfs1(int x,int f,int depth)
{
    size[x] = 1,fa[x] = f,dep[x] = depth;
    int maxson = -1;
    for(int i = head[x];i;i = e[i].next)
    {
    if(e[i].to == f) continue;
    dfs1(e[i].to,x,depth+1);
    size[x] += size[e[i].to];
    if(size[e[i].to] > maxson) maxson = size[e[i].to],hson[x] = e[i].to;
    }
}

void dfs2(int x,int t)
{
    top[x] = t,dfn[x] = ++idx;
    if(!hson[x]) return;
    dfs2(hson[x],t);
    for(int i = head[x];i;i = e[i].next)
    {
    if(e[i].to == fa[x] || e[i].to == hson[x]) continue;
    dfs2(e[i].to,e[i].to);
    }
}

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]];
    }
    if(dep[x] > dep[y]) swap(x,y);
    return x;
}

int main()
{
    n = read(),q = read();
    rep(i,1,n-1) x = read(),y = read(),add(x,y),add(y,x);
    dfs1(1,0,1),dfs2(1,1);
    rep(i,1,q)
    {
    a = read(),b = read(),c = read(),d = read();
    int l1 = lca(a,b),l2 = lca(c,d);
    if(dep[l1] >= dep[l2])
    {
        if(lca(l1,c) == l1 || lca(l1,d) == l1) printf("Y
");
        else printf("N
");
    }
    else if(dep[l2] >= dep[l1])
    {
        if(lca(l2,a) == l2 || lca(l2,b) == l2) printf("Y
");
        else printf("N
");
    }
    }
    return 0;
}