最近公共祖先问题（LCA）

最近公共祖先问题（LCA）

(下面的内容来自算法艺术与信息学竞赛一书)

LCA问题：给出一个有根树T，对于任意两个节点u和v,求出 LCA(T, u, v).即离根最远的结点x，使得x同时是u和v的祖先。

把LCA问题看成询问式的：给出一系列询问，程序当对每一个询问尽快做出反应。对于这类问题有两种解决方法：（1）在线算法(online-algorithm)：用比较长的时间做预处理，但是等信息充足之后每次回答询问只需要用较少的时间。(2)离线算法(offline-algorithm):先把所有的询问读入，然后一起把所有的询问回答完成。

最简单的在线算法是先对所有可能的O(n*n)种询问计算出结果，然后每次询问都可以在O(1)的时间内直接得到结果。可以把它转换为O(n*n)次单个的LCA计算。

单个的LCA问题的朴素计算：从u的父亲开始顺着树向上枚举u的祖先并保存在一个列表L中，然后在再用类似的方法枚举v,当第一次发现某个祖先x在L中，则输出x.由于L可以达到O(n)的.所以用此法的在线算法的时间复杂度下限为O(n*n*n).

在线LCA问题的O(n*n)---O(1)的算法：令L(u)为u的深度。不妨设L(u)<=L(v),则如果u是v的父亲，LCA(u,v)=u;否则LCA(u,v)=LCA(u,father(v)).这样递推的时间复杂度为O(n*n),即预处理的时间为O(n*n),O(1)的询问时间解决了LCA问题。

从上面的递推方法，给我们一个启示。当L(u)<=L(v)时，可以根据LCA(u,v)的答案把所有结点分成若干个等价类，u的子树上节点v都满足LCA(u,v)=u;u的父亲fahter(u)的任何不以u为根的子树上的结点v都满足LCA(u,v)=father(u);father(fahter(u))的任何不以fahter(u)为根的子树上节点v都满足LCA(u,v)=fahter(father(u));...........

LCA问题的Tarjan算法：用LCA(root(T))调用下面的过程，算法将会回答所有的询问。

//merge():表示把u和v所在的集合合并，u为集合的代表元。find（）表示找出集合的代表元。可以看出，在任何时侯一个集合里面的元素都形成了一颗树。
//每处理完一颗子树就把它并到父亲所在的集合中。该算法执行的是深度优先遍历，因此对于任何处理过的节点v,v当前所在的集合的代表元就是v和当前处理结点u的LCA。
//算法的巧妙之处在于利用了并查集。使得和当前处理元素u有关的所有询问都可以立即得出，而不需要一一计算。
void LCA(u) {
    makeSet(u);
    ancestor[find(u)] = u;
    for(u的每个孩子v){
        LCA(v);
        merge(u, v);
        ancestor[find(u)] = u;
    }
    visit[u] = true;
    for(Q(u)中的每个元素v){
        if(visit[v] == true) printf(ancestor[find(v)]);
    }
}