神秘国度的爱情故事(树剖+lca)

数据结构课程设计

题目

神秘国度的爱情故事

[问题描述]

某个太空神秘国度中有很多美丽的小村,从太空中可以想见,小村间有路相连,更精确一点说,任意两村之间有且仅有一条路径。小村 A 中有位年轻人爱上了自己村里的美丽姑娘。每天早晨,姑娘都会去小村 B 里的面包房工作,傍晚 6 点回到家。年轻人终于决定要向姑娘表白,他打算在小村 C 等着姑娘路过的时候把爱慕说出来。问题是,他不能确定小村 C 是否在小村 B 到小村 A 之间的路径上。你可以帮他解决这个问题吗?

[基本要求]

(1)输入由若干组测试数据组成。每组数据的第 1 行包含一正整数 N ( l 《 N 《 50000 ) , 代表神秘国度中小村的个数,每个小村即从0到 N - l 编号。接下来有 N -1 行输入,每行包含一条双向道路的两个端点小村的编号,中间用空格分开。之后一行包含一正整数 M ( l 《 M 《 500000 ) ,代表着该组测试问题的个数。接下来 M 行,每行给出 A 、 B 、 C 三个小村的编号,中间用空格分开。当 N 为 O 时,表示全部测试结束,不要对该数据做任何处理。

(2)对每一组测试给定的 A 、 B 、C,在一行里输出答案,即:如果 C 在 A 和 B 之间的路径上,输出 Yes ,否则输出 No.

思路:

题干中得出任意两个村有且仅有一条路径,所以这是一个n个节点n-1条边无向连通图,可以构成一颗树。

 

题目中说明了要判断c是不是在ab路径上,所以可以想到要找c是不是在ab路径上,要通过遍历ab时是否经过了c,所以这里可以采用图的方式来处理这颗树,存储方式是链式前向星,遍历是用dfs也就是深度优先搜索。

 

首先,存储方式是用链式前向星,优点是这种建图和遍历图的效率较其他方式高(邻接表的静态实现,节省了分配内存的时间和空间)。

 

如果采用深度优化搜索,最坏的情况是每个节点都要遍历一次,所以时间复杂度是O(n)。每个测试数据都要处理一遍,所以时间复杂度是O(m),m是测试数据的个数,每个测试数据都要跑一遍dfs,所以总的时间复杂度是O(n*m),这里的n和m的最大值都很大,所以很耗时间。

 

所以我们这里采取树剖法和最近公共祖先lca进行优化,优化之后的时间复杂度就是O(n*log(m))。

 

最近公共祖先,顾名思义,就是两个节点的共同祖先且是深度最大的节点。思路就是让ab中深度大的结点先往上走到和深度小的结点同深度,然后两个结点同时往上走并判断是否相等,相等即找到最近公共祖先,在这个过程中要判断是否经过c。

 

判断条件如下图:如果ac的lca等于c且bc的lca等于c,则判断ab的lca是不是等于c,如果是,则c在ab路径上,如果不是,则不在。

如果 ac的lca等于c或者bc的lca等于c,则说明c一定在ab路径上,因为如果ac的lca等于c,bc的lca不等于c,则说明c是a的祖先节点,则c一定在ab上。反之,说明c是b的祖先节点,则c一定在ab上。其他情况都是c不在ab路径上。

但只使用最近公共祖先lca是不行的,算法复杂度没有得到优化,找最近公共祖先是一层层往上跳的,最坏的情况下,复杂度也还是O(n*m),所以这里使用了树剖来解决问题。

 

树剖就是树链剖分,用于将树分割成若干条链的形式,以维护树上路径的信息。也就是将整棵树剖分为若干条链,使它组合成线性结构,维护链的信息。树剖有很多种方法,这次实验使用了重链剖分。

 

重链剖分可以将树上的任意一条路径划分成不超过log(n)条连续的链,每条链上的点深度互不相同(即是自底向上的一条链,链上所有点的 LCA 为链的一个端点)。

 

在剖分时优先遍历重子节点,最后树的dfn序上,重链的dfn序是连续的。按dfn排序后的序列既是剖分后的链。

将一颗树剖分成若干链的好处就是,由于链的长度不超过log(n),进行预处理,时间复杂度会退化到O(log(m)),所以最坏的情况下,找到最近公共祖先lca的时间复杂度为O(n*log(m))。

 

通过树剖来求解lca,我觉得也是一种倍增的思想。我们将一颗树预处理成若干链。每条链都有一个top值,若a和b的top值不同,说明a和b是在不同的重链上,这时比较两个重链顶端的深度大小,深度较大的那条链往上跳,  直至同一条链,往上跳是直接跳到它链首的父节点。这样,当跳到同一条链上时,深度较小的那个点就是两个点的lca。

 

然后通过如上所述的判断方法,就可以求解出题目答案了。

实验代码
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5e5+5; 
struct edge{
    int to,ne;
}e[MAXN << 1];
int n,m,s,ecnt,head[MAXN],dep[MAXN],siz[MAXN],son[MAXN],top[MAXN],f[MAXN];
/*
使用链式前向星建图,双向边 
head存的是上一条边的编号 
*/ 
void add(int x,int y)
{
    e[++ecnt].to=y;//终点 
    e[ecnt].ne=head[x];//以x为起点的上一条边的编号 
    head[x]=ecnt;//更新以x为起点的上一条边编号 
    //双向边建立,该题是无向图,因为两个节点都可能是父节点或者子节点,所以需要建双边 
    e[++ecnt].to=x;
    e[ecnt].ne=head[y];
    head[y]=ecnt;
}
/*
                        树链剖分--重链剖分 
    将一颗树分成若干条链,每条链的长度不超过log(m),链上的点的深度互不相同,
    链是自底而上,链上所有点的lca构成链的端点。 
*/ 
/*
第一个dfs 找出子数大小(size),深度(deep),节点的父节点(f)
重儿子son  
*/ 
void dfs1(int x,int fath,int deep)
{ 
    f[x]=fath; 
    siz[x]=1;
    dep[x]=deep;
    //遍历 
    for(int i=head[x];i!=-1;i=e[i].ne)
    {
        int v=e[i].to;
        if(v==f[x])continue;//如果v等于father,跳过 
        dfs1(v,x,deep+1);//fath 现在变成x 
        siz[x]+=siz[v];//加上每个重儿子的size 
        if(!son[x]||siz[son[x]]<siz[v])//如果这个重孩子的数量大于最大的重孩子数量 
            son[x]=v;//这个点的重孩子就是v 
    }
}
/*
第二个dfs 找出节点所在重链的顶部节点top 
*/
void dfs2(int x,int tv)
{
    top[x]=tv;//x最上面的元素是tv 
    if(son[x])dfs2(son[x],tv);//如果有重儿子节点,直接dfs他的重儿子,重儿子优先 
    //遍历轻儿子 
    for(int i=head[x];i!=-1;i=e[i].ne)
    {
        int v=e[i].to;
        if(v==f[x]||v==son[x])continue;//跟dfs1差不多,不过多了一个判断是否是重儿子 
        dfs2(v,v);//以v为开头的新的链 
    }
}
/*
求最近公共祖先 
*/ 
int lca(int x,int y){ 
     while(top[x]!=top[y]){ //如果是不同重链 
        if(dep[top[x]]>=dep[top[y]])x=f[top[x]];//重链顶端深度较大的链向上跳,跳到链首的父节点,直至同一条链 
        else y=f[top[y]];
    }
    return dep[x]<dep[y]?x:y;//当跳到同一条链上时,深度较小的节点就是lca 
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    memset(head,-1,sizeof(head));//初始化为-1 
    scanf("%d",&n);
    for(int i=1;i<n;++i)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y); 
    }
    dfs1(0,0,0);
    dfs2(0,0);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        int x,y,z;
        int a,b,c,ans;
        scanf("%d%d%d",&a,&b,&c);
        ans=0;
        int XY=lca(a,b);
        int XZ=lca(a,c);
        int YZ=lca(b,c);
       // cout<<XY<<" "<<XZ<<" "<<YZ<<endl; 
        /*如果ac的lca等于c且bc的lca等于c,则判断ab的lca是不是等于c,
        如果是,则c在ab路径上,如果不是,则不在。 
        如果 ac的lca等于c或者bc的lca等于c,则说明c一定在ab路径上,
        因为如果ac的lca等于c,bc的lca不等于c,则说明c是a的祖先节点,则c一定在ab上
        反之,说明c是b的祖先节点,则c一定在ab上
        其他情况都是c不在ab路径上 
        */ 
        if(XZ==c&&YZ==c){
            if(c==XY)
                ans=1;
            else
                ans=0;
        }else if(XZ==c||YZ==c){
            ans=1;
        }else{
            ans=0;
        }
        if(ans) printf("Yes\n");
        else printf("No\n");
    }
}
实验结果:

在本校OJ上AC了本题。

点赞
  1. 麦客说道:

    能不能增加显示点赞数

发表评论

昵称和uid可以选填一个,填邮箱必填(留言回复后将会发邮件给你)
tips:输入uid可以快速获得你的昵称和头像

open

该博客目前已迁移到另外一个站点链接——http://blog.datealive.top/。需要更换友链请前往此站进行交换,望谅解