LCA 在线倍增法 求最近公共祖先

第一步：建树  这个就不说了

第二部:分为两步  分别是深度预处理和祖先DP预处理

DP预处理：

int i,j;

     for(j=;(<<j)<n;j++)

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

        if(fa[i][j]=-)

          fa[i][j]=fa[fa[i][j-]][j-];/*DP处理出i的2^j祖先是谁*/

深度预处理：

 void dfs(int now,int from,int deepth)

 {

      deep[now]=deepth;

      for(int i=head[now];i;i=e[i].pre)

        if(e[i].v!=from)

          dfs(e[i].v,now,deepth+);

 }

第三部分：LCA核心

 int LCA(int a,int b)// 求a、b的最近公共祖先

 {

     int i,j;

     if(deep[a]<deep[b]) swap(a,b); // 保证a的深度比b大这样便于操作

     for(i=;(<<i)<=deep[a];++i);// (1<<i) 等同于2的i次方

          i--;

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

       if((deep[a]-(<<j))>=deep[b])// 让a节点往上蹦 直到a、b晚上一蹦就重合

         a=fa[a][j];

     if(a==b)return a;// 如果a的一个祖先恰好是b

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

       if(fa[a][j]!=-&&fa[a][j]!=fa[b][j])// 没有越界并且祖先不同  那么就让a,b同时往上蹦

         {

           a=fa[a][j];

           b=fa[b][j];

         }

     return fa[a][];

 }

默写的代码：

 void DP {

     int i,j;

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

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

             if(fa[i][j]=-)

                 fa[i][j]=fa[fa[i][j-]][j-];

     }

 }

 void dfs(int now,int deepth,int from) {

     deep[now]=deepth;

     for(int i=head[now]; i; i=e[i].next) {

         if(e[i].v!=from) {

             dfs(e[i].v,deepth+,now);

         }

     }

 }

 int LCA(int a,int b) {

     int i,j;

     if(deep[a]<deep[b]) swap(a,b);

     for(i=; (<<i)<=deep[a]; i++);

     i--;

     for(j=i; j>=; j--) {

         if(deep[a]-(<<j)>=deep[b])

             a=fa[a][j];

     }

     if(a==b) return a;

     for(j=i; j>=; j--) {

         if(fa[a][j]!=-&&fa[a][j]!=fa[b][j]) {

             a=fa[a][j];

             b=fa[b][j];

         }

     }

     return fa[a][];

 }