倍增法求LCA

倍增法求LCA

LCA（Least Common Ancestors）的意思是最近公共祖先，即在一棵树中，找出两节点最近的公共祖先。

倍增法是通过一个数组来实现直接找到一个节点的某个祖先，这样我们就可以在O(logn)的时间内求出求出任意节点的任意祖先。

然后先把两个节点中转化为深度相同的节点，然后一起向上递增，知道找到相同的节点，该节点就是这两个节点的最近公共祖先。

代码实现：

 #include<cstdio>

 #include<iostream>

 #define N 42000

 using namespace std;

 int next[N],to[N],head[N],num,deep[N],father[N][],n,m,p,a,b,c;

 void add(int false_from,int false_to){

     next[++num]=head[false_from];

     to[num]=false_to;

     head[false_from]=num;

 }

 void dfs(int x){

     deep[x]=deep[father[x][]]+;

     for(int i=;father[x][i];i++)

         father[x][i+]=father[father[x][i]][i];

     for(int i=head[x];i;i=next[i])

         if(!deep[to[i]]){

             father[to[i]][]=x;

             dfs(to[i]);

         }

 }

 int lca(int x,int y){

     if(deep[x]>deep[y])

         swap(x,y);

     for(int i=;i>=;i--)

         if(deep[father[y][i]]>=deep[x])

             y=father[y][i];

     if(x==y)

         return y;

     for(int i=;i>=;i--)

         if(father[y][i]!=father[x][i]){

             y=father[y][i];

             x=father[x][i];

         }

     return father[x][];

 }

 int main(){

     scanf("%d%d%d",&n,&m,&p);

     for(int i=;i<n;++i){

         scanf("%d%d",&a,&b);

         add(a,b);

         add(b,a);

     }

     dfs(p);

     for(int i=;i<=m;++i){

         scanf("%d%d",&a,&b);

         printf("%d ",lca(a,b));

     }

     return ;

 }

预处理复杂度：O(nlogn)。

一组询问复杂度：O(logn)。

空间复杂度：O(nlogn)。

在线算法。