LCA问题(least Common Ancestors,最近公共祖先问题),是指给定一棵有根树T,给出若干个查询LCA(u,v)(通常查询数量较大),每次求树T中两个顶点u和v的最近公共祖先,即找到一个节点...然后我们要查询两个节点的最近公共祖先,只需要找到两个节点往上找时,第一个相同的祖先。
为每个节点标记好它的父节点只需要维持一个数组_father[n],然后在深度遍历的时候存在来就好。...假设我们当前需要查询节点u和节点v的公共祖先,我们在后序遍历的过程中,假设现在我们已经访问到节点u,对于节点v只有两种形式,一是被访问过,二是还没被访问。...但是这个跳的方法和以往的不一样,它是以按2的次幂的形式跳,也就是跳2^0,2^1,2^2等等层。因为对于任意一个整数n,它都可以找到唯一的一组x1,x2,x3,….....scanf("%d", &m); //查询个数
while (m--)
{
int u, v; scanf("%d%d", &u, &v);//查询u和v的LCA
printf("%d和%d的最近公共祖先为