原题链接： 仓鼠找sugar

题意：
给出一个 $n$ 个点的无根树，$m$ 次询问，每次给出两对点，询问两条路径是否有交集。
$n \leq 1e5, m \leq 1e5$

设给出的四个点为 $a, b, c, d$
记 $x = lca(a, b)$，$y = lca(c, d)$

性质1：
如果两条路径有交集，则必有 $x$ 在 $c-d$ 路径上或 $y$ 在 $a-b$ 路径上

性质2：
如果点 $u$ 在 $a - b$ 路径上，则有 $depth[u] \geq depth[x]$ 且 $(lca(a, u) == u$ 或 $lca(b, u) == u)$

就来存一下这个结论，证明不会qaq

C++代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std;

typedef long long LL;

const int N = 100010, M = N * 2;

int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
    e[idx] = b;
    ne[idx] = h[a];
    h[a] = idx ++;
}

int n, m;
int depth[N], fa[N][18];
int q[N];

void bfs()
{
    memset(depth, -1, sizeof depth);
    depth[1] = 0;

    int hh = 0, tt = -1;
    q[++ tt] = 1;

    while(hh <= tt)
    {
        int u = q[hh ++];

        for(int i = h[u]; ~i; i = ne[i])
        {
            int j = e[i];
            if(depth[j] == -1)
            {
                depth[j] = depth[u] + 1;
                q[++ tt] = j;

                fa[j][0] = u;
                for(int k = 1; k < 18; k ++)
                    fa[j][k] = fa[fa[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a, int b)
{
    if(depth[a] < depth[b])  swap(a, b);

    for(int i = 17; i >= 0; i --)
        if(depth[fa[a][i]] >= depth[b])
            a = fa[a][i];

    if(a == b)  return a;

    for(int i = 17; i >= 0; i --)
        if(fa[a][i] != fa[b][i])
        {
            a = fa[a][i];
            b = fa[b][i];
        }
    return fa[a][0];
}

int main()
{
    memset(h, -1, sizeof h);

    scanf("%d%d", &n, &m);
    for(int i = 1; i < n; i ++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        add(b, a);
    }

    bfs();

    while(m --)
    {
        int a, b, c, d;
        scanf("%d%d%d%d", &a, &b, &c, &d);

        int x = lca(a, b),  y = lca(c, d);

        if( depth[x] >= depth[y] and (lca(x, c) == x or lca(x, d) == x) or 
            depth[y] >= depth[x] and (lca(y, a) == y or lca(y, b) == y))  puts("Y");
        else  puts("N");
    }
    return 0;
}