当前位置:首页 > 图论 > 最近公共祖先 > 正文
洛谷P3379【模板】最近公共祖先(LCA)
5162+

题目大意:给定一棵有根多叉树,请求出指定两个点直接最近的公共祖先。

输入输出格式

输入格式:

第一行包含三个正整数N、M、S,分别表示树的结点个数、询问的个数和树根结点的序号。

接下来N-1行每行包含两个正整数x、y,表示x结点和y结点之间有一条直接连接的边(数据保证可以构成树)。

接下来M行每行包含两个正整数a、b,表示询问a结点和b结点的最近公共祖先。

输出格式:

输出包含M行,每行包含一个正整数,依次为每一个询问的结果。

输入输出样例

输入样例#1:

5 5 4
3 1
2 4
5 1
1 4
2 4
3 2
3 5
1 2
4 5

输出样例#1:

4
4
1
4
4

说明

时空限制:1000ms,128M

数据规模:

对于30%的数据:N<=10,M<=10

对于70%的数据:N<=10000,M<=10000

对于100%的数据:N<=500000,M<=500000

解题思路

1、tarjan算法:这是一种离线算法,首先分别对边和询问建立邻接表,其原理是利用搜索的后续遍历,将搜索完的点的祖先修改成最小搜索子树的根,需要结合并查集。搜索过程中,先扫一遍与该点相关的询问,如果询问的另外一个点已经搜索过,那么该点的祖先就是当前最小搜索子树的根,也即最近公共祖先。接着再搜索该点的子树,搜索完的点更新自己的祖先为父亲结点。虽然自己的祖先总是自己或者父亲结点,但通过并查集可以快速压缩路径,找到最近公共祖先;虽然遍历某个点的询问时,有些点还没访问过,但是那些没访问过的点,总会被搜索到,这是这两个点的最近公共祖先也就能求出来。

2、倍增算法:这是一种在线算法,首先建立边的邻接表,从跟开始搜索一步,预处理出各个点的深度和父亲结点;接着,预处理每个点往上走2步、4步、8步……分别到达那个结点,这样往上爬,速度比一步一步要快很多很多;最后就可以在线求两个点的最近公共祖先了,如果两个点深度不一样,让深度大的点先爬上去,使其深度一样,如果深度一样但不相同,那么公共祖先还在上面,就一起往上爬,直到爬到公共祖先的儿子,最后再爬一步就是公共祖先了。

问题1:为什么一直往上爬就能爬到深度相同?

不妨设深度差为x,那么x用二进制来表示,1的位置就怕对应2的多少次方不,必能爬到相同深度。

问题2:为什么最后只爬到最近公共祖先的儿子,不直接爬上去?

因为最近公共祖先上面的都是公共祖先,爬太高了,不能确定公共祖先是否是最近的。

问题3:为什么先爬2的19次方,再爬2的18次方……

因为先爬小的,不能确定是否是必须爬的。

程序实现

About

坚决不Copy代码!

本文标签:,,,,,,

洛谷P3379【模板】最近公共祖先(LCA):等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!