首页 > 代码库 > 求LCA——倍增
求LCA——倍增
本代码写的也许有错误，欢迎各位大佬查找其中的错误（位运算不太会）。
首先在这里不得不提的是——倍增是一种思想，没有一种特殊的框架或者模板之类的东西，有的人认为倍增竟然有模板这种东西。这与这种想法大佬给出的评论是
好吧，也许这是来自大佬的嘲讽，或者是说大佬这在传递一种思想。
倍增思想是一种十分巧妙的思想,在当今的信息学竞赛中应用得十分广泛。本质思想:每次根据已经得到的信息,将考虑的范围扩大一倍,从而加速操作。
我们开始讲倍增求LCA：
题目：口胡的——题意：给你一个森林，m个询问:v,p。求有多少个点（除v外） 与 v的第p个祖先相同？
LCA指的是最近公共祖先(Least Common Ancestors)，那怎么求呢？最粗鄙的方法就是先dfs一次，处理出每个点的深度，然后把深度更深的那一个点一个点地一个点地往上跳，直到到某个点和另外那个点的深度一样，然后两个点一起一个点地一个点地往上跳，直到到某个点（就是最近公共祖先）两个点“变”成了一个点。
下面代码就诞生了：
1 const int POW = 18; 2 void dfs(int u , int fa){ 3 d[u] = d[fa] + 1; 4 p[u][0] = fa; 5 for(int i = 1; i < POW ; i ++) p[u][i] = p[p[u][i - 1]][i - 1]; 6 int sz = edge[u].size(); 7 for(int i = 0 ; i < sz ; i ++){ 8 int v = edge[u][i]; 9 if(v == fa) continue; 10 dfs(v , u); 11 } 12 }
不过有没有发现一个点地一个点地跳很浪费时间？如果一下子跳到目标点内存又可能不支持，相对来说倍增的性价比算是很高的，倍增的话就是一次跳2i 个点，不难发现深度差为x时，深度更深的那个点就需要跳x个点。
我们采用倍增：//a ^= b ^= a ^= b;此句感谢ZHT纠错 ； 非位运算乃RQY大佬所改
1 int lca( int a , int b ){ 2 if( d[a] > d[b] ) a ^= b ^= a ^= b; 3 if( d[a] < d[b] ){ 4 int del = d[b] - d[a]; 5 for( int i = 0; i < POW ; i ++ ) if(del & (1 << i)) b = p[b][i]; 6 } 7 if( a != b ){ 8 for( int i = POW - 1; i >= 0; i -- ) 9 if( p[a][i] != p[b][i] )10 a = p[a][i] , b = p[b][i];11 a = p[a][0] , b = p[b][0]; 12 } 13 return a; 14 }
1 if (d[a] > d[b]) a ^= b ^= a ^= b;2 if (d[a] < d[b]) {3 int del = d[a] - d[b];4 int t = 1, i = 0;5 while (t < del) t *= 2, ++i;6 for (; t; t /= 2, --i) if (del >= t) { b = p[b][i]; del -= t; }7 }8 //...
注：上下合并一起看是完整代码；
求LCA——倍增
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。