洛谷 P3398 仓鼠找sugar 题解【tarjan】【LCA】

点击量：147

   LCA还能这样玩；

目录

题目描述

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

 

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

 

输入输出格式

输入格式：

第一行两个正整数n和q，表示这棵树节点的个数和询问的个数。

 

接下来n-1行，每行两个正整数u和v，表示节点u到节点v之间有一条边。

 

接下来q行，每行四个正整数a、b、c和d，表示节点编号，也就是一次询问，其意义如上。

 

输出格式：

对于每个询问，如果有公共点，输出大写字母“Y”；否则输出“N”。

 

输入输出样例

输入样例#1：

5 5

2 5

4 2

1 3

1 4

5 1

5 1

2 2

1 4

4 1

3 4

3 1

1 5

3 5

1 4

输出样例#1：

Y

N

Y

Y

Y

说明

本题时限1s，内存限制128M，因新评测机速度较为接近NOIP评测机速度，请注意常数问题带来的影响。

 

20%的数据 n<=200,q<=200

 

40%的数据 n<=2000,q<=2000

 

70%的数据 n<=50000,q<=50000

 

100%的数据 n<=100000,q<=100000

题解：

   对于这种一眼看不出来解法却隐约看得出算法的题，我的做法是编数据+手玩数据。因为这是一棵树，所以有根据深度的层次关系。如果树上两条链相交，那么一定是以下几种情况：

   因为这是全部可能的情况（相交或覆盖），可以发现，较低的lca一定在较高的lca所在链上，换句话说，较低lca一定是两链的交点。因为在树上的两节点深度相同时，它们一定都不是lca，也一定不是交点；而同等深度不同的两个点不可能为祖孙关系，因此lca一定是交点，不然就不满足父亲的唯一性。

   这样一来我们只要验证较低的lca是否在较高lca连接两点所在链上就够了。但我们总不能在100,000规模下跑a到bO(n)的遍历检验能否遍历到所求lca吧，所以验证一个点c是否在树链(a,b)上，手玩几下就会发现如果在，那么c一定是lca(a,c)或lca(b,c)，因为此时c比lca(a,b)要深（非严格），比a或b要浅；如果都不是，就输出”N”，至少有一个是就输出”Y”。

Code：

#include<cstdio>
#include<cstring>

struct edge
{
    int n,nxt,cnt;
    bool used;
    edge(int n,int nxt,int cnt)
    {
        this->n=n;
        this->nxt=nxt;
        this->cnt=cnt;
        used=false;
    }
    edge(int n,int nxt)
    {
        this->n=n;
        this->nxt=nxt;
        used=false;
    }
    edge()
    {
        nxt=-1;
        used=false;
    }
}e[201000],a[401000];
int head[101000],ecnt=-1;
int heada[101000],acnt=-1;
void add(int from,int to)//树边
{
    e[++ecnt]=edge(to,head[from]);
    head[from]=ecnt;
    e[++ecnt]=edge(from,head[to]);
    head[to]=ecnt;
}
void adda(int from,int to,int cnt)//询问边
{
    a[++acnt]=edge(to,heada[from],cnt);
    heada[from]=acnt;
    a[++acnt]=edge(from,heada[to],cnt);
    heada[to]=acnt;
}
struct mouse
{
    int a,b,c,d;
    mouse(int a,int b,int c,int d)
    {
        this->a=a;
        this->b=b;
        this->c=c;
        this->d=d;
    }
    mouse(){}
}ask[101000];
bool vis[101000];
int fa[101000];
int deep[101000];//对于第i个询问，较深的最近公共祖先是多少
int ans[101000][2];
int d[101000];
int my_find(int x)
{
    if(fa[x]==x)
        return x;
    return fa[x]=my_find(fa[x]);
}
void tarjan(int x,int from)
{
    vis[x]=true;
    for(int i=head[x];~i;i=e[i].nxt)
        if(e[i].n!=from)
        {
            d[e[i].n]=d[x]+1;
            tarjan(e[i].n,x);
        }

    for(int i=heada[x];~i;i=a[i].nxt)
        if(!a[i].used&&vis[a[i].n])
        {
            a[i].used=true;
            a[i^1].used=true;
            ans[a[i].cnt/2][a[i].cnt&1]=my_find(a[i].n);
        }
    fa[x]=from;
}
int main()
{
    memset(head,-1,sizeof(head));
    memset(heada,-1,sizeof(heada));
    int n,q,u,v;
    scanf("%d%d",&n,&q);
    for(int i=1;i<n;i++)
    {
        fa[i]=i;
        scanf("%d%d",&u,&v);
        add(u,v);
    }
    fa[n]=n;
    for(int i=1;i<=q;i++)
    {
        scanf("%d%d%d%d",&ask[i].a,&ask[i].b,&ask[i].c,&ask[i].d);
        adda(ask[i].a,ask[i].b,2*i);
        adda(ask[i].c,ask[i].d,2*i+1);
    }
    d[1]=1;
    tarjan(1,1);
    memset(heada,-1,sizeof(heada));//多次初始化
    acnt=-1;
    for(int i=1;i<=q;i++)
    {
        if(d[ans[i][0]]<d[ans[i][1]])
        {
            deep[i]=ans[i][1];
            adda(ans[i][1],ask[i].a,2*i);
            adda(ans[i][1],ask[i].b,2*i+1);
        }
        else
        {
            deep[i]=ans[i][0];
            adda(ans[i][0],ask[i].c,2*i);
            adda(ans[i][0],ask[i].d,2*i+1);
        }
    }
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        fa[i]=i;
    tarjan(1,1);
    for(int i=1;i<=q;i++)
        if(ans[i][0]==deep[i]||ans[i][1]==deep[i])
            puts("Y");
        else
            puts("N");
    return 0;
}