最近公共祖先LCAC++版.docx
- 文档编号:1114212
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:38
- 大小:750.41KB
最近公共祖先LCAC++版.docx
《最近公共祖先LCAC++版.docx》由会员分享,可在线阅读,更多相关《最近公共祖先LCAC++版.docx(38页珍藏版)》请在冰点文库上搜索。
最近公共祖先LCAC++版
LCA最近公共祖先
首先是最近公共祖先的概念(什么是最近公共祖先?
):
在一棵没有环的树上,每个节点肯定有其父亲节点和祖先节点,而最近公共祖先,就是两个节点在这棵树上深度最大的公共的祖先节点。
换句话说,就是两个点在这棵树上距离最近的公共祖先节点。
所以LCA主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径。
有人可能会问:
那他本身或者其父亲节点是否可以作为祖先节点呢?
答案是肯定的,很简单,按照人的亲戚观念来说,你的父亲也是你的祖先,而LCA还可以将自己视为祖先节点。
举个例子吧,如下图所示4和5的最近公共祖先是2,5和3的最近公共祖先是1,2和1的最近公共祖先是1。
这就是最近公共祖先的基本概念了,那么我们该如何去求这个最近公共祖先呢?
通常初学者都会想到最简单粗暴的一个办法:
对于每个询问,遍历所有的点,时间复杂度为O(n*q),很明显,n和q一般不会很小。
常用的求LCA的算法有:
Tarjan/DFS+ST/倍增
后两个算法都是在线算法,也很相似,时间复杂度在O(logn)~O(nlogn)之间。
什么是Tarjan(离线(塔尔杨))算法呢?
顾名思义,就是在一次遍历中把所有询问一次性解决,所以其时间复杂度是O(n+q)。
Tarjan算法的优点在于相对稳定,时间复杂度也比较居中,也很容易理解。
下面详细介绍一下Tarjan算法的基本思路:
1.任选一个点为根节点,从根节点开始。
2.遍历该点u所有子节点v,并标记这些子节点v已被访问过。
3.若是v还有子节点,返回2,否则下一步。
4.合并v到u上。
5.寻找与当前点u有询问关系的点v。
6.若是v已经被访问过了,则可以确认u和v的最近公共祖先为v被合并到的父亲节点a。
遍历的话需要用到dfs来遍历(我相信来看的人都懂吧...),至于合并,最优化的方式就是利用并查集来合并两个节点。
下面上伪代码:
1Tarjan(u)//marge和find为并查集合并函数和查找函数
2{
3foreach(u,v)//访问所有u子节点v
4{
5Tarjan(v);//继续往下遍历
6marge(u,v);//合并v到u上
7标记v被访问过;
8}
9foreach(u,e)//访问所有和u有询问关系的e
10{
11如果e被访问过;
12u,e的最近公共祖先为find(e);
13}
14}
个人感觉这样还是有很多人不太理解,所以我打算模拟一遍给大家看。
建议拿着纸和笔跟着我的描述一起模拟!
!
假设我们有一组数据9个节点8条边联通情况如下:
1--2,1--3,2--4,2--5,3--6,5--7,5--8,7--9即下图所示的树
设我们要查找最近公共祖先的点为9--8,4--6,7--5,5--3;
设f[]数组为并查集的父亲节点数组,初始化f[i]=i,vis[]数组为是否访问过的数组,初始为0;
下面开始模拟过程:
取1为根节点,往下搜索发现有两个儿子2和3;
先搜2,发现2有两个儿子4和5,先搜索4,发现4没有子节点,则寻找与其有关系的点;
发现6与4有关系,但是vis[6]=0,即6还没被搜过,所以不操作;
发现没有和4有询问关系的点了,返回此前一次搜索,更新vis[4]=1;
表示4已经被搜完,更新f[4]=2,继续搜5,发现5有两个儿子7和8;
先搜7,发现7有一个子节点9,搜索9,发现没有子节点,寻找与其有关系的点;
发现8和9有关系,但是vis[8]=0,即8没被搜到过,所以不操作;
发现没有和9有询问关系的点了,返回此前一次搜索,更新vis[9]=1;
表示9已经被搜完,更新f[9]=7,发现7没有没被搜过的子节点了,寻找与其有关系的点;
发现5和7有关系,但是vis[5]=0,所以不操作;
发现没有和7有关系的点了,返回此前一次搜索,更新vis[7]=1;
表示7已经被搜完,更新f[7]=5,继续搜8,发现8没有子节点,则寻找与其有关系的点;
发现9与8有关系,此时vis[9]=1,则他们的最近公共祖先为find(9)=5;
(find(9)的顺序为f[9]=7-->f[7]=5-->f[5]=5return5;)
发现没有与8有关系的点了,返回此前一次搜索,更新vis[8]=1;
表示8已经被搜完,更新f[8]=5,发现5没有没搜过的子节点了,寻找与其有关系的点;
发现7和5有关系,此时vis[7]=1,所以他们的最近公共祖先为find(7)=5;
(find(7)的顺序为f[7]=5-->f[5]=5return5;)
又发现5和3有关系,但是vis[3]=0,所以不操作,此时5的子节点全部搜完了;
返回此前一次搜索,更新vis[5]=1,表示5已经被搜完,更新f[5]=2;
发现2没有未被搜完的子节点,寻找与其有关系的点;
又发现没有和2有关系的点,则此前一次搜索,更新vis[2]=1;
表示2已经被搜完,更新f[2]=1,继续搜3,发现3有一个子节点6;
搜索6,发现6没有子节点,则寻找与6有关系的点,发现4和6有关系;
此时vis[4]=1,所以它们的最近公共祖先为find(4)=1;
(find(4)的顺序为f[4]=2-->f[2]=2-->f[1]=1return1;)
发现没有与6有关系的点了,返回此前一次搜索,更新vis[6]=1,表示6已经被搜完了;
更新f[6]=3,发现3没有没被搜过的子节点了,则寻找与3有关系的点;
发现5和3有关系,此时vis[5]=1,则它们的最近公共祖先为find(5)=1;
(find(5)的顺序为f[5]=2-->f[2]=1-->f[1]=1return1;)
发现没有和3有关系的点了,返回此前一次搜索,更新vis[3]=1;
更新f[3]=1,发现1没有被搜过的子节点也没有有关系的点,此时可以退出整个dfs了。
经过这次dfs我们得出了所有的答案,有没有觉得很神奇呢?
是否对Tarjan算法有更深层次的理解了呢?
如果有什么不懂可以在下面留言提问or发送问题到1136404654@。
推荐几道LCA的题目
CODEVS2370小机房的树 传送门
CODEVS1036商务旅行 传送门
METOCODE223拉力赛 传送门
HDU2586Howfarway?
传送门
ZOJ3195 Designthecity 传送门
CODEVS1036商务旅行
题目描述Description
某首都城市的商人要经常到各城镇去做生意,他们按自己的路线去做,目的是为了更好的节约时间。
假设有N个城镇,首都编号为1,商人从首都出发,其他各城镇之间都有道路连接,任意两个城镇之间如果有直连道路,在他们之间行驶需要花费单位时间。
该国公路网络发达,从首都出发能到达任意一个城镇,并且公路网络不会存在环。
你的任务是帮助该商人计算一下他的最短旅行时间。
输入描述InputDescription
输入文件中的第一行有一个整数N,1<=n<=30000,为城镇的数目。
下面N-1行,每行由两个整数a和b(1<=a,b<=n;a<>b)组成,表示城镇a和城镇b有公路连接。
在第N+1行为一个整数M,下面的M行,每行有该商人需要顺次经过的各城镇编号。
输出描述OutputDescription
在输出文件中输出该商人旅行的最短时间。
样例输入SampleInput
5
12
15
35
45
4
1
3
2
5
样例输出SampleOutput
7
#include
structnode{intto,next,ljj;}e[60001],qe[60001];
intn,m,fa[30001],head[30001],qhead[30001],ans=0,cnt=0,pjy[30001];
boolb[30001],bb[30001];
intask(intx)
{
if(x==fa[x])returnfa[x];
returnfa[x]=ask(fa[x]);
}
voidaddedge(intx,inty)
{
e[++cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
voidaddedge2(intx,inty,intz)
{
qe[++cnt].to=y;
qe[cnt].ljj=z;
qe[cnt].next=qhead[x];
qhead[x]=cnt;
}
voidtarjan(intu)
{
b[u]=1;fa[u]=u;
for(inti=head[u];i;i=e[i].next)
if(!
b[e[i].to])
{
pjy[e[i].to]=pjy[u]+1;
tarjan(e[i].to);
fa[e[i].to]=u;
}
for(inti=qhead[u];i;i=qe[i].next)
if(b[qe[i].to]&&!
bb[qe[i].ljj])
{
ans+=pjy[qe[i].to]+pjy[u]-2*pjy[ask(qe[i].to)];
bb[qe[i].ljj]=1;
}
}
intmain()
{
scanf("%d",&n);
intx,y;
for(inti=1;i { scanf("%d%d",&x,&y); addedge(x,y); addedge(y,x); } cnt=0; intT; scanf("%d",&T); scanf("%d",&x); for(inti=2;i<=T;i++) { scanf("%d",&y); addedge2(x,y,i-1); addedge2(y,x,i-1); x=y; } pjy[1]=0; tarjan (1); printf("%d",ans); return0; } /* 离线tarjan+并查集. 关于邻接链表边的标号的初始化问题. 若第一条边标号为0则需初始化head[1~n]=-1, 因为搜索的时候必定会搜到head[u]==0 然后需判i! =-1 若第一条边编号为1则只需判i! =0 无需初始化. 切记. */ #include #include #include #defineMAXN50001 usingnamespacestd; intn,m,head[MAXN],ans,fa[MAXN],lc[MAXN],tot,cut,deep[MAXN],head2[MAXN]; boolb[MAXN],b2[MAXN]; structdata { intv; intnext; } e[MAXN<<1],s[MAXN<<1]; voidadd_edge(intu,intv) { e[tot].v=v; e[tot].next=head[u]; head[u]=tot++; } voidadd(intu,intv) { s[cut].v=v; s[cut].next=head2[u]; head2[u]=cut++; } voiddfs(intx,intfather) { deep[x]=deep[father]+1; b[x]=true; for(inti=head[x];i! =-1;i=e[i].next) { if(! b[e[i].v])dfs(e[i].v,x); } } intfind(intx) { if(x==fa[x])returnfa[x]; returnfa[x]=find(fa[x]); } voidlcatarjan(intu) { fa[u]=u;b[u]=true; for(inti=head[u];i! =-1;i=e[i].next) { if(b[e[i].v])continue; lcatarjan(e[i].v); fa[find(e[i].v)]=find(u); lc[find(u)]=u; } for(inti=head2[u];i;i=s[i].next) { if(b2[s[i].v]) { ans+=deep[u]+deep[s[i].v]-2*deep[lc[find(s[i].v)]]; } } b2[u]=true; } intmain() { memset(head,-1,sizeof(head)); memset(head2,-1,sizeof(head2)); intx,y; scanf("%d",&n); for(inti=1;i { scanf("%d%d",&x,&y); add_edge(x,y); add_edge(y,x); } intu=1,v; scanf("%d",&m); for(inti=1;i<=m;i++) { scanf("%d",&v); add(u,v); add(v,u); u=v; } dfs(1,0); memset(b,0,sizeof(b)); lcatarjan (1); printf("%d",ans); return0; } /* 第一种,倍增(O(nlogn)~O(logn),在线): 倍增的思想用在树上,即可以求出lca。 我们维护二维数组,f[i][j],表示i号点的第2^j号祖先,显然2^0=1也就是f[i][0]就是他的父亲 我们需要用dfs维护一个深度数组(求lca需要用) 还需要倍增求出所有的f[i][j],学过st的都应该知道,在这里 f[i][j]=f[f[i][j-1]][j] 然后是我们的求lca了,很简单,首先要将这两个点u和v调到同一深度,这样以后操作都是同深度的。 怎么调深度呢? 很简单,将他们的深度相减,我们设为dep,那么这个dep的就对应了深一点的那个点需要上升的高度,恩,应该马上能想到,直接用二进制表示深度然后一直爬上去就行了,这就是倍增的思想,log级别 同一深度时,我们要同时上升啦~我们继续用倍增思想,依次上升2^k的高度。 什么时候上升呢? 当然是f[u][k]! =f[v][k]的时候,因为这说明他们的祖先还不同,他们位于2棵子树,所以要上升。 并且顺序要从大到小! 否则求不到最小的祖先,很容易理解的。 */ #include #include #include #defineMAXN30001 #defineD20 usingnamespacestd; structdata { intv; intnext; intz; }e[MAXN*2]; inttot,deep[MAXN],fa[MAXN][D+5],n,m,head[MAXN]; voidadd_edge(intu,intv) { tot++; e[tot].v=v; e[tot].next=head[u]; head[u]=tot; } voiddfs(intnow,intfather,intd)//建树. { fa[now][0]=father; deep[now]=d; for(inti=head[now];i;i=e[i].next) { if(father! =e[i].v) { dfs(e[i].v,now,d+1); } } } voidget_father()//处理出每个节点的2^j. { for(intj=1;j<=D;j++) for(inti=1;i<=n;i++) fa[i][j]=fa[fa[i][j-1]][j-1]; } intget_same(inta,intb)//二进制使u,v在同一深度. { for(inti=0;i<=D;i++) if(b&(1< returna; } intlca(intu,intv) { if(deep[u] u=get_same(u,deep[u]-deep[v]);//lca if(u==v)returnu;//u是v父亲时. for(inti=D;i>=0;i--)//向上搜到lca的儿子. if(fa[u][i]! =fa[v][i]) { u=fa[u][i]; v=fa[v][i]; } returnfa[u][0];//此时u为lca的子节点. } intmain() { scanf("%d",&n); intx,y; for(inti=1;i<=n-1;i++)//▲一般是n-1条边. { scanf("%d%d",&x,&y); add_edge(x,y); add_edge(y,x); } dfs(1,1,0); get_father(); intu,v; tot=0; scanf("%d%d",&m,&u); for(inti=1;i { scanf("%d",&v); intLCA=lca(u,v); tot+=(deep[u]+deep[v]-2*deep[LCA]);//数学方法. u=v; } printf("%d",tot); return0; } CODEVS2370小机房的树 题目描述Description 小机房有棵焕狗种的树,树上有N个节点,节点标号为0到N-1,有两只虫子名叫飘狗和大吉狗,分居在两个不同的节点上。 有一天,他们想爬到一个节点上去搞基,但是作为两只虫子,他们不想花费太多精力。 已知从某个节点爬到其父亲节点要花费c的能量(从父亲节点爬到此节点也相同),他们想找出一条花费精力最短的路,以使得搞基的时候精力旺盛,他们找到你要你设计一个程序来找到这条路,要求你告诉他们最少需要花费多少精力 输入描述InputDescription 第一行一个n,接下来n-1行每一行有三个整数u,v,c。 表示节点u爬到节点v需要花费c的精力。 第n+1行有一个整数m表示有m次询问。 接下来m行每一行有两个整数u,v表示两只虫子所在的节点 输出描述OutputDescription 一共有m行,每一行一个整数,表示对于该次询问所得出的最短距离。 样例输入SampleInput 3 101 201 3 10 20 12 样例输出SampleOutput 1 1 2 数据范围及提示DataSize&Hint 1<=n<=50000,1<=m<=75000,0<=c<=1000 #include #include #defineM1000001 usingnamespacestd; intf[M][31]; intdis[M]; structnode{ intto,next; intval; }; nodee[M]; inttot,head[M]; intn,m; intdeep[M]; inlineintread(int&x){ x=0;charc=getchar(); while(c>'9'||c<'0')c=getchar(); while(c>='0'&&c<='9')x=10*x+c-48,c=getchar(); } inlinevoiddfs(intnow,intfrom,intdep,intv){ deep[now]=dep; f[now][0]=from; dis[now]=v+dis[from]; for(inti=head[now];i;i=e[i].next){ intu=e[i].to; if(u! =from)dfs(u,now,dep+1,e[i].val); } } /*inlinevoiddfs(intu,intdep){//两种dfs姿势都可以 deep[u]=dep; for(inti=head[u];i;i=e[i].next){ intv=e[i].to; if(! deep[v]&&v){ f[v][0]=u; dis[v]=dis[u]+e[i].val; dfs(v,dep+1); } } }*/ inlinevoidadd(intx,inty,intz){ e[++tot].to=y; e[tot].val=z; e[tot].next=head[x]; head[x]=tot; } inlineintLCA(inta,intb){ intans=0; if(deep[a] intt=deep[a]-deep[b]; for(inti=0;i<=30;i++) if((1< if(a==b)returna; for(inti=30;i>=0;i--) if(f[a][i]! =f[b][i]) a=f[a][i],b=f[b][i]; returnf[a][0]; } intmain(){ read(n); for(inti=1;i intx,y,z; read(x);read(y);read(z);
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 最近 公共 祖先 LCAC
![提示](https://static.bingdoc.com/images/bang_tan.gif)