Llf's blog

标签 tarjan 下的文章

April 10, 2018

LCA问题总结

概述 最近公共祖先(LCA)问题指的是在一棵树中,求出任意两个点的最近的公共祖先。如在下图中: 2号节点和1号节点的LCA是4,3号和2号的LCA也是4. 求LCA的方法主要有:暴力,倍增,RMQ和Tarjan。 这篇文章以洛谷P3379 【模板】最近公共祖先(LCA)为例。 Tarjan算法 Tarjan算法能够通过dfs将树上节点信息和查询的信息一次性解决,但是无法应对存在修改的情况,...