最低共同祖先(boost图)

在中找到算法 Wikipedia

 function TarjanOLCA(u)
 MakeSet(u);
 u.ancestor := u;
 for each v in u.children do
     TarjanOLCA(v);
     Union(u,v);
     Find(u).ancestor := u;
 u.colour := black;
 for each v such that {u,v} in P do
     if v.colour == black
         print "Tarjan's Least Common Ancestor of " + u +
               " and " + v + " is " + Find(v).ancestor + ".";

我找到了以下网站,可以回答您的问题: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest%20Common%20Ancestor%20%28LCA%29

其基本思想是将“最低共同祖先”问题转化为另一个“范围最小查询”问题,然后用O(N)+O(1)方法求解。我还没有彻底研究过,但它似乎有很好的记录,值得一看。