LCA

/ 0评 / 0

最近学了LCA的相关问题在此总结下

在有根树中,两个节点u和v的公共祖先中距离最近的那个成为其最近公共祖先,在树上两点因为存在唯一的最短路,故其LCA为最短路上深度最小的点。通过求解LCA我们可以处理如求解树或DAG上任意两点的最短距离,将RMQ转化为LCA,结合树链剖分操作等。
求解$LCA$的各种方法全部以HDU 2586为例(自娱自乐)

Tarjan离线处理

离线$ tarjan$的思想是在处理完以$ u$为根的子树时,就将该子树和父亲节点$ u$合并,这样处理完子树后就可以回答所有关于$ u$的询问,前提是询问的节点都是已经被访问过的。为此我们需要为查询建立一颗查询树并存好询问顺序。

Tarjan代码

ST+dfs求解LCA

该算法是将$LCA$转换成$RMQ$问题,好处是通过对区间预处理能高效$O(1)$在线回答,所用思想是将树形结构通过欧拉游记录任意节点的深度,其子树规模,及欧拉序。
这里我废话下$ LCA$与$RMQ$的关系,老是会忘是不是无药可救了。

倍增算法求解LCA待补

发表评论

电子邮件地址不会被公开。 必填项已用*标注