第一步：建樹 ?這個就不說了

第二部:分為兩步 ?分別是深度預處理和祖先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 }

?

轉載于:https://www.cnblogs.com/suishiguang/p/6103780.html

總結

以上是生活随笔為你收集整理的LCA 在线倍增法 求最近公共祖先的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。