P3398 仓鼠找sugar

\(Description\)

有一颗\(n\)个节点的树，给你两条路径各自的端点\(a->b、c->d\)，询问这两条路径是否有公共点

\(Solution\)

判断树上两条路径有无公共点：求\(LCA\)
若两条路径有公共点，那么到达公共点可以选择顺着链往上走或者往下拐进另一颗子树。
进一步说，向上走的路只有一条，两条链有公共点后一起往上走到最后一个公共点一定有一条链结束或者是往下拐

结合这张图看的更明白
所以说一定有一条链两端点的\(LCA\)位于另一条链上，这是两条链相交的充要条件
设这个点为\(c\)，这个点位于的链的两个端点为\(a,b\),\(a,b\)的\(LCA\)为\(d\)，\(dis(a,d)+dis(d,c)+dis(b,c)=dis(a,b)\)
根据树上路径只有一条的性质，\(dis(a,c)+dis(c,b)=dis(a,b)\)

又因为可能\(X\)链的\(LCA\)位于\(Y\)链上，反过来也有可能，所以两种情况验证取\(or\)即可

\(Code\)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cmath>
#define re register
#define maxn 200010
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1; char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int q,a,b,c,d;
int tmp1,tmp2,tmp3,n,x,y,vis[maxn],f[maxn][23],lg[maxn],root;
int cnt,head[maxn],dep[maxn];
struct Edge{
    int v,nxt;
}e[maxn<<2];
inline void add(int u,int v)
{
    e[++cnt].v=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void dfs(int now,int fa)
{
    dep[now]=dep[fa]+1;
    f[now][0]=fa;
    for(int i=1;(1<<i)<=dep[now];++i)
     f[now][i]=f[f[now][i-1]][i-1];
    for(int i=head[now];i;i=e[i].nxt)
    {
        int ev=e[i].v;
        if(ev==fa) continue;
        dfs(ev,now);
    }
}
int lca(int x,int y)
{
    if(dep[y]>dep[x]) swap(x,y);
    for(re int i=lg[dep[x]-dep[y]];i>=0;--i)
    {
        if(dep[f[x][i]]<dep[y]) continue;
        x=f[x][i];
    }
    if(x==y) return x;
    for(re int i=lg[dep[x]-1];i>=0;--i)
    {
        if(f[x][i]==f[y][i]) continue;
        x=f[x][i],y=f[y][i];
    }
    return f[x][0];
}
void pre()
{
    tmp1=1,tmp2=0;
    while(tmp1<=n)
    {
        lg[tmp1]=tmp2;
        tmp2++;
        tmp1*=2;
    }
    for(re int i=1;i<=n;++i)
    {
        if(lg[i]) continue;
        lg[i]=lg[i-1];
    }
}
int dis(int a,int b)//计算一条链的长度
{
    re int c=lca(a,b);
    return abs(dep[a]-dep[c])+abs(dep[b]-dep[c]);
}
int main()
{
    n=read(),q=read();
    pre();
    for(re int i=1;i<n;++i)
    {
        x=read(),y=read();
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    for(re int i=1;i<=q;++i)
    {
        a=read(),b=read(),c=read(),d=read();
        tmp1=lca(a,b);
        tmp2=lca(c,d);
        if(dis(a,tmp2)+dis(b,tmp2)==dis(a,b)||dis(c,tmp1)+dis(d,tmp1)==dis(c,d)) printf("Y\n");
        else printf("N\n");
    }
    return 0;
}