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

作者: wjyyy 分类: LCA,tarjan,,解题报告 发布时间: 2018-07-11 22:50

点击量:18

 

 

   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;
}

说点什么

avatar
  Subscribe  
提醒
/* */