仓鼠找sugar(LCA)

小仓鼠的和他的基（mei）友（zi）sugar住在地下洞穴中，每个节点的编号为1~n。地下洞穴是一个树形结构。这一天小仓鼠打算从从他的卧室（a）到餐厅（b），而他的基友同时要从他的卧室（c）到图书馆（d）。他们都会走最短路径。现在小仓鼠希望知道，有没有可能在某个地方，可以碰到他的基友？

小仓鼠那么弱，还要天天被zzq大爷虐，请你快来救救他吧！

Solution

这题数据不是很强，可以用两个log水过(考场上就这么写的）。但还有更优秀的一个log的做法。

我们对于两对点，分别求出它们的LCA。

如果两组LCA是同一个点，那么路径肯定有交。

如果其中一个LCA比其它两个点还要深，那么路径肯定没有交。

两种极端情况考虑完了。

这时如果路径有交那么，其中一个lca一定是另外一组点中其中一个点的祖先。

Code

#include<iostream>

#include<cstdio>

#include<cmath>

#define N 200009

using namespace std;

int p[N][],head[N],deep[N],a,b,c,d,tot,n,q;

struct ssd

{

    int n,to;

}an[N<<];

inline void add(int u,int v)

{

    an[++tot].n=head[u];

    an[tot].to=v;

    head[u]=tot;

}

void dfs(int u,int fa)

{

    deep[u]=deep[fa]+;

    p[u][]=fa;

    for(int i=;(<<i)<=deep[u];++i)

      p[u][i]=p[p[u][i-]][i-];

    for(int i=head[u];i;i=an[i].n)

    {

        int v=an[i].to;

        if(v!=fa)dfs(v,u);

    }

}

int lca(int u,int v)

{

    if(deep[u]<deep[v])swap(u,v);

    for(int i=;i>=;--i)

      if(deep[u]-(<<i)>=deep[v])u=p[u][i];

     if(u==v)return u;

    for(int i=;i>=;--i)

      if(p[u][i]!=p[v][i])u=p[u][i],v=p[v][i];

     return p[u][];

}

int main()

{

    scanf("%d%d",&n,&q);

    for(int i=;i<n;++i)

      scanf("%d%d",&a,&b),add(a,b),add(b,a);

    dfs(,);

    while(q--)

    {

        scanf("%d%d%d%d",&a,&b,&c,&d);

        int l1=lca(a,b),l2=lca(c,d);

        if(l1==l2)printf("Y\n");

        else if(deep[l1]>max(deep[c],deep[d])||deep[l2]>max(deep[a],deep[b]))printf("N\n");

        else

        {

            if(deep[l1]>deep[l2]){swap(l1,l2);swap(a,c);swap(b,d);}

            int l3=lca(l2,a),l4=lca(l2,b);

            if(l3==l2||l4==l2)printf("Y\n");

            else printf("N\n");

        }

   }

    return ;

}