LCA

LCA

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

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

luoyayu