LCA学习笔记
祖先的定义
如果学习树结构就会明白除了根节点以外每个节点都有一个父节点,所以我们定义祖先为父节点的父节点,然后我们给出最近公共祖先的定义
一棵树祖先中到两个点距离最近的节点。
能够解决LCA问题的方式有很多,所以作为一个ACM选手,肯定是我全都要
解决方案
欧拉序
树的欧拉序是对树进行dfs的一种序列,他有两条性质
- 在每个节点进和出都加入序列
- 只要到达每一个节点就把他加入序列
那么我们寻找他们的最近公共祖先就可以从第一次出现第一个节点和第一次出现的第二个节点之间节点中深度最大的节点。
HDOJ[2586]
1 |
|
Trajan算法
首先Trajan是一个离线算法,在一次遍历中把所有询问一次解决,时间复杂度$O(n+q)$。
我也想自己写啊,但是就是不会啊,自己想是不可能自己想的,只要抄抄别人的博客才能维持生活。
- 任选择一个点作为根节点,从根节点开始
- 遍历该节点的所有子节点,并标记这些子节点$v$已经被访问过
- 如果$v$还有子节点,返回2,否则就进入下一步
- 合并$v$到$u$。
- 寻找与当前点$u$有询问关系的点$v$
- 若是$v$已经被访问过了,则可以确定$u$和$v$的最近公共祖先为$v$被合并的父亲节点$fa[u]$。
1 |
|
RMQ算法(ST表)
其实这个方法也就是欧拉序加上RMQ,在第一个解决方案中我们使用枚举来寻找他们的LCA,这也导致时间复杂度变成了$O(n^2)$。而寻找固定区间内的最小值是一个很普遍的问题,也就是RMQ。而解决RMQ有很多种$O(logn)$的方法,
- 线段树、树状数组
- ST表
他们均可以有效地解决区间最值问题。
例题[hdoj5044]
使用方法为 RMQ+正负tag
详情见我刷的LCA专题训练。
Reference:https://blog.csdn.net/czl_233/article/details/78368927
http://www.cppblog.com/menjitianya/archive/2015/12/10/212447.html