首页 > 代码库 > LCA 在线倍增法 求最近公共祖先
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节点往上蹦 蹦到和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 }
LCA 在线倍增法 求最近公共祖先
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。