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

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

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

DP预处理：

int i,j;
     for(j=1;(1<<j)<n;j++)
       for(int i=0;i<n;++i)
        if(fa[i][j]=-1)
          fa[i][j]=fa[fa[i][j-1]][j-1];/*DP处理出i的2^j祖先是谁*/

深度预处理：

1 void dfs(int now,int from,int deepth)
2 {
3      deep[now]=deepth;
4      for(int i=head[now];i;i=e[i].pre)
5        if(e[i].v!=from)
6          dfs(e[i].v,now,deepth+1);
7 }

第三部分：LCA核心

 1 int LCA(int a,int b)// 求a、b的最近公共祖先 
 2 {
 3     int i,j;
 4     if(deep[a]<deep[b]) swap(a,b); // 保证a的深度比b大这样便于操作 
 5     for(i=0;(1<<i)<=deep[a];++i);// (1<<i) 等同于2的i次方 
 6          i--;
 7     for(j=i;j>=0;j--)
 8       if((deep[a]-(1<<j))>=deep[b])// 让a节点往上蹦 直到a、b晚上一蹦就重合 
 9         a=fa[a][j];
10     if(a==b)return a;// 如果a的一个祖先恰好是b 
11     for(j=i;j>=0;j--)
12       if(fa[a][j]!=-1&&fa[a][j]!=fa[b][j])// 没有越界并且祖先不同  那么就让a,b同时往上蹦 
13         {
14           a=fa[a][j];
15           b=fa[b][j];
16         }
17     return fa[a][0];
18 }

默写的代码：

 1 void DP {
 2     int i,j;
 3     for(int j=1; (1<<j)<n; j++) {
 4         for(int i=0; i<n; i++)
 5             if(fa[i][j]=-1)
 6                 fa[i][j]=fa[fa[i][j-1]][j-1];
 7     }
 8 }
 9 void dfs(int now,int deepth,int from) {
10     deep[now]=deepth;
11     for(int i=head[now]; i; i=e[i].next) {
12         if(e[i].v!=from) {
13             dfs(e[i].v,deepth+1,now);
14         }
15     }
16 }
17 int LCA(int a,int b) {
18     int i,j;
19     if(deep[a]<deep[b]) swap(a,b);
20     for(i=0; (1<<i)<=deep[a]; i++);
21     i--;
22     for(j=i; j>=0; j--) {
23         if(deep[a]-(1<<j)>=deep[b])
24             a=fa[a][j];
25     }
26     if(a==b) return a;
27     for(j=i; j>=0; j--) {
28         if(fa[a][j]!=-1&&fa[a][j]!=fa[b][j]) {
29             a=fa[a][j];
30             b=fa[b][j];
31         }
32     }
33     return fa[a][0];
34 }

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

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