【刷题】【LCA】小仓鼠找糖

思路图片均来自luogu

题意：现有A,B,C,D四点，判断A到B的最短路，和C到D的最短路有无交汇

首先，建MST，然后LCA就是他的最短路径的回头点，且这是唯一路径

上图体会一下：

先看3个点之间，问A->B,A->C之间有没有重合部分

从回头点的角度看，LCA(A,B)=x,LCA(A,C)=y;

如果x比y深度大，那么A->y点，就会拐弯向下，

重叠部分就是A->y

反之就是A->x

再来看4个点之间，

问题能够变成什么样呢：

现在我们知道了 x=LCA(A,B),y=LCA(C,D);

问A->x->B,C->y->D是否有重合部分，

=》

假设图中只有这两条路了，问A能不能到C/D

A这个人走路只能直走，拐弯，直走，

那么看这个拐弯的点，在不在A->B上，

就是

max(dep[LCA(A,C)] ,dep[LCA(A,D)] ) >= dep[LCA(A,B) ]

只要满足一组，就有重合部分，其他的式子就必定成立（从定义出发证明）

所以写出完整式子

max(dep[LCA(A,C)] ,dep[LCA(A,D)] ) >= dep[LCA(A,B) ]

|| max(dep[LCA(B,C)] ,dep[LCA(B,D)] ) >= dep[LCA(A,B) ]

|| max(dep[LCA(A,C)] ,dep[LCA(B,C)] ) >= dep[LCA(C,D) ]

|| max(dep[LCA(A,D)] ,dep[LCA(B,D)] ) >= dep[LCA(C,D) ]

化简：

max(dep[LCA(A,C)] ,dep[LCA(A,D)] ,dep[LCA(B,C)] ,dep[LCA(B,D)] ) >= min( dep[LCA(A,B) ],dep[LCA(C,D) ] );

代码：

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<algorithm>
using namespace std;
int n,q;
const int N=100003;
int fa[N],dep[N];
int son_sz[N],son[N],top[N];
vector <int> g[N];

void dfs1(int u,int f)
{
    fa[u]=f,dep[u]=dep[f]+1;
    son_sz[u]=1;
    int sz=g[u].size() ;
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        if(v==f) continue;
        dfs1(v,u);
        son_sz[u]+=son_sz[v];
        
        if(son_sz[v]>son_sz[son[u]]) son[u]=v;
    }
}
void dfs2(int u,int tp)
{
    top[u]=tp;
    if(!son[u]) return ;
    
    dfs2(son[u],tp);
    int sz=g[u].size() ;
    for(int i=0;i<sz;i++)
    {
        int v=g[u][i];
        if(v==fa[u] || v==son[u]) continue;        
        dfs2(v,v);
    }
}

int LCA(int u,int v)
{
    while(top[u]!=top[v])
    {
        if(dep[top[u]]>dep[top[v]])
            u=fa[top[u]];
        else v=fa[top[v]];
    }    
    return dep[u]<dep[v] ? u :v;
}

int main()
{
    scanf("%d%d",&n,&q);
    int u,v;
    for(int i=1;i<n;i++)
        scanf("%d %d",&u,&v),g[u].push_back(v),g[v].push_back(u);
    
    dfs1(1,0);
    dfs2(1,1);
     
    int s1,s2,ed1,ed2;
    while(q--)
    {
        scanf("%d%d%d%d",&s1,&ed1,&s2,&ed2);
        int t2=dep[LCA(s1,ed1)],t1=dep[LCA(s2,ed2)];
        
        int p1=dep[LCA(s1,s2)],p2=dep[LCA(s1,ed2)];
        int p3=dep[LCA(ed1,s2)],p4=dep[LCA(ed1,ed2)];
        
        if(max(max(p1,p2),max(p3,p4)) >= max(t1,t2))printf("Y
");
        else printf("N
");
    }
    
    return 0;
}