洛谷3398 仓鼠找sugar

题意

有一棵 $N$ 点的树，有 $Q$ 次询问 $(a,b,c,d)$ ，问 $a\rightarrow b$ 与 $c\rightarrow d$ 是否相交。

$N,Q\le 100000$ 。

题解

可以发现两条边相交，就一定存在一条边的最高点在另一条边上，即端点的 $\text{LCA}$ 。

所以只用求 $\text{LCA}$ 就行了。第一次写倍增 $\text{LCA}$ ，感觉还是树剖好啊。

#include<bits/stdc++.h>

using namespace std;

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

struct Edge {
    int next,to;
} edge[200005];
int cnt,head[100005],n,m,a,b,c,d,fa[100005][18],deep[100005],lg[100005];

inline void add(int u,int v)
{
    edge[++cnt].to=v;
    edge[cnt].next=head[u];
    head[u]=cnt;
}

void dfs1(int x,int f,int dep)
{
    deep[x]=dep;
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        fa[y][0]=x;
        dfs1(y,x,dep+1);
    }
}

void dfs2(int x,int f)
{
    for (int i=1;i<=lg[deep[x]];i++) fa[x][i]=fa[fa[x][i-1]][i-1];
    for (int i=head[x];i;i=edge[i].next)
    {
        int y=edge[i].to;
        if (y==f) continue;
        dfs2(y,x);
    }
}

inline int lca(int u,int v)
{
    if (deep[u]<deep[v]) u^=v^=u^=v;
    while (deep[u]>deep[v]) u=fa[u][lg[deep[u]-deep[v]]];
    if (u==v) return u;
    for (int i=lg[deep[u]];~i;i--) if (fa[u][i]^fa[v][i]) u=fa[u][i],v=fa[v][i];
    return fa[u][0];
}

signed main()
{
    n=read(); m=read();
    for (int i=1;i<n;i++)
    {
        a=read(); b=read();
        add(a,b);
        add(b,a);
    }
    for (int i=1;i<=n;i++)
    {
        lg[i]=lg[i-1];
        if (1<<(lg[i]+1)==i) lg[i]++;
    }
    dfs1(1,0,1);
    dfs2(1,0);
    for (int i=1;i<=m;i++)
    {
        a=read(); b=read(); c=read(); d=read();
        int lca1=lca(a,b),lca2=lca(c,d);
        if (deep[lca1]<deep[lca2]) swap(a,c),swap(b,d),swap(lca1,lca2);
        if (lca(lca1,c)==lca1 || lca(lca1,d)==lca1) puts("Y");
        else puts("N");
    }
    return 0;
}