Tarjan's offline algorithm for computing LCA

Tarjan离线算法求LCA介绍

前言 ：一开始掌握Tarjan算法的核心思想。在阅读了许多大牛的博客后，在反复推敲之后发现自己的理解还不够深入。如果看完本文后仍不理解其中的细节，则建议先尝试解决裸题HDU2586，并通过编写代码来实践 Tarjan 算法的应用，并观察其运行效果。如果觉得不够深入，则可以选择其他文章继续学习。

一：概念介绍

1：最近公共祖先

我们考虑rooted tree Tree中的两个节点u和v，并定义它们的最近公共祖先（LCA）为一个节点x，使得x既是u和v的共同祖先，并且具有最大的深度值。另一种理解方式则是将树Tree视为一个无向无环图，则其LCA即为连接u与v路径上深度最低的那个节点。

（图一中LCA(2,5)应修改为1，感谢评论区网友的指正~）

2：并查集：详见http://baike.baidu.com/view/521705.htm

3：离线算法：

算法的设计策略主要建立在执行前已知输入数据的基本假设之上。换言之，在处理开始之前就必须明确所有问题相关的信息，并且一旦解决问题就需要立即给出相应的结果。通常这类基于完全