2018-03-1018:04:55在图论和计算机科学中，最近公共祖先，LCA(LowestCommonAncestor)是指在一个树或者有向无环图中同时拥有v和w作为后代的最深的节点。计算最近公共祖先往往是很有用的，比如在计算树中两个节点的距离的时候，可以分别计算根到各个节点的距离，然后计算根到最近公共祖先的距离，用...

Tarjan(离线)算法的基本思路及其算法实现　　　　首先是最近公共祖先的概念(什么是最近公共祖先？)：　　　　在一棵没有环的树上，每个节点肯定有其父亲节点和祖先节点，而最近公共祖先，就是两个节点在这棵树上深度最大的公共的祖先节点。　　　　换句话说，就是两个点在这棵树上距离最近的公共祖先节点。　　　　所以LCA主要是用...