# **倍增** # **【序言】** 我认为吧，所有能够优化复杂度的算法都是神奇的，所有能够化繁琐为形象的文字都是伟大的。一直觉得倍增算法是个很神奇的东西，所以决定写点东西纪念一下它。但是作为一个非常不称职的ACMER(JBER)，我非常讨厌在看别人的算法解析时整版的i，j，k等我看到鼠标就惯性移到右上角的符号语言，所以我想用最形象的方式来纪念它 **【一】** 从前，有一只可爱得不得了的小白兔，它想从A地去往遥远的B地。  **2B小白兔：**             向右边跳一步，左边跳一步，再向右边跳很多步，再……（对不起，这个太脑残了） **普通小白兔：**             向右边跳一步，再跳一步，再跳一步……再跳一步，哇，到了！好开心！ **超级小白兔：**         向右边跳一大步，一步跳到B，然后默默回头，鄙视一下那只一步一步跳的小白兔。         我相信作为一个正常人，是不会考虑到2B小白兔的这种做法的，因为它太脑残了。         同时我也相信，作为一个正常人，也不会考虑到超级小白兔的这种做法的 **【二】**         从前，有一只可爱得不得了的小白兔，它想从A地去往遥远的B、C、D、E、F这几个让它魂牵梦萦的地方。（不要问我从哪里来，我的梦想在远方）  **普通小白兔：**             一步又一步，生命不息，跳跃不止。 **超级小白兔：**             一步到B，再一步到C，再一步到D，再一步到E，再一步到F，完工。 **写给普通小白兔的话：** 亲爱的小白兔，我知道你勇毅，你质朴，但是，苦海无涯，回头是岸。 **写给超级小白兔的话：** 我不知道你的小抄本是否还够用，我不知道你摸着黑就出门是为了什么，你不觉得你的行踪早就已经暴露了吗？你以为你很聪明吗？不，你错了，你就一下酒菜，永远都是，因为你不知道倍增算法，这是你失败的根源，再见，我心中永远不会逝去的蠢兔子。 > 普通兔子 \= 速度慢，无资源损耗 || 超级兔子 \= 速度快，多资源损耗 ***** **1** 还记得那只离我们远去的2B兔子吗？对，其实我们早该想到了，越蠢得不可思议的兔子身上竟然有巨大的宝藏，再看看它的名字吧，“2B”！去掉一个“B”！就是“2”！对，你没有听错，就是“2”，你能想到4、8、16、32吗？ **2** 再想想，超级兔子的小抄本不够用，不就是因为它为了应对所有的目的地信息，它记录下了任何一个格子跳任意步会到达的格子，100个格子它要记录大概5000条信息，1000个格子大概要记录500000条信息，10000个格子它大概要记录50000000条信息，至于你晕没晕，我相信它应该晕了。 **3** 可不可以把记录的信息数降到最低呢？当然可以，2B兔子帮你忙，让你用2战胜敌人。 **4** 当你只记录任何一个格子跳1、2、4、8、16……步会到达的格子的时候，你有没有发现信息数突然少了好多好多啊！真的少了好多好多啊！100个格子只要500条左右，1000个格子只要5000条左右，10000个格子只要50000条左右，不比不知道，一比吓一跳啊！ **从此，超级小白兔成为了聪明小白兔，它的生活是这样的：**  在夜深人静的时候，它偷偷出门做小抄，记录下从每个格子跳1、2、4、8……个格子后会到达的格子，然后在太阳出来后，它在众目睽睽之下，开始了表演。 从A出发：若跳8个格子（超过B了，放弃） 若跳4个格子（超过B了，放弃） 若跳2个格子（没超过B，跳吧） 若跳1个格子（没超过B，跳吧） 从B出发：………… 多么轻松的事情，只要一本很薄的小抄就可以了，最关键的是：它绝对不会连着跳两步都是跳相同的格子数，因为如果跳两次2个格子都是可行的话，那么它干嘛不跳4个格子捏？ ## 我们可是从多到少来判断的啊！！ **好的，聪明小白兔白天的事情你已经看懂了，且看它晚上是怎么打小抄的吧。**  从A出发跳1步到1（记录下来） 从1出发跳1步到2（记录下来） ………… （跳1步的记录完毕） 从A出发跳2步？就是从A出发跳1步再跳1步的到的地方，翻看小抄，直接誊写从1出发跳1步会到的2这个格子作为A跳2步会到的格子。 从1出发跳2步？跟刚才一样，直接誊写。 ………… （跳2步的记录完毕） 从A出发跳4步？你还真去跳4步？不，它也就是等于从A出发跳2步到的2号点再跳2步会到的格子，那么我们直接誊写2号格子跳2步会到的格子就可以了。 …… …… 看看聪明小白兔多么聪明！也许还有自认为更聪明的： “在记录A跳4步会到的格子的时候，为什么不直接从A跳4步看到了哪里再记录下来呢？跳4步跟跳1步的代价不是一样的么” ...... “我这样回答你好了！把你丢在纽约的一个公交车站，问你一条线路的下一个站是什么？你怎么办？当然是自己亲自走到下一个站就知道了！那如果问你接下来的第4个站是什么？难道你可以直接走到第4个站而不用途径其它的站点了吗？这不现实，你还是要一个一个站的走，因为关键在于你只能知道你目前所在站点的下一个站是什么，想知道下下个站，除非你已经到了下个站，兔子跳格子也跟这类似，虽然聪明小白兔神通广大，但是不至于伟大到可以提前预知跳几步会到哪里啊！！” # 完 [原文链接](https://blog.csdn.net/jarjingx/article/details/8180560) [来意道例题压压惊](http://acm.hdu.edu.cn/showproblem.php?pid=2586) 题目大意：给一个无根树，有q个询问，每个询问两个点，问两点的距离。 思路 : 应该是LCA的裸题，因为是树求一下最近公共祖节点，然后记录一下路径长度就行了，但是因为是无根树，所以需要选一个点作为根节点，我选 1 号节点 **AC code** ``` c++ #include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #include <vector> #include <cmath> using namespace std; const int maxn = 4e4+50; const int logtwo = 30; struct edge{ //邻接表构图 int to ,w ; edge(){} edge(int _w,int _to){ w = _w; to = _to; } }; vector<edge>G[maxn]; int grand[maxn][logtwo],depth[maxn],gw[maxn][logtwo]; //depth当前点的深度 // grand[x][i]表示x的2^(i-1)的父亲是谁 //gw[x][i]表示x到x的2^(i-1)的父亲处需要的花费 int n,m,N; // n点的数量，m边的数量 N 兔子最多跳的步数 void dfs(int x) { //dfs获取每一个树上点的深度 for (int i = 1;i <= N ; i ++) { grand[x][i] = grand[grand[x][i-1]][i-1]; // x的2^(i-1)的父亲 = x的2^(i-2)的父亲 的 // 2^(i-2) 的父亲 即 2^(i-1) = 2^(i-2) +2^(i-2) gw[x][i] = gw[grand[x][i-1]][i-1] + gw[x][i-1]; //跟上文grand的计算一样 } int len = G[x].size(); for (int i = 0;i < len ; i ++ ) { //基本操作dfs edge e = G[x][i]; if ( grand[x][0] != e.to ) { depth[e.to] = depth[x] + 1 ; grand[e.to][0] = x; gw[e.to][0] = e.w; dfs(e.to); } } } void init() { // 初始化函数 N = floor( log(n + 0.0) / log(2.0) ); memset(depth,0,sizeof(depth)); memset(grand,0,sizeof(grand)); memset(gw,0,sizeof(gw)); dfs(1); } int lca(int a,int b) { //先将两个点的深度变为一致 if ( depth[a] > depth[b] ) swap(a,b); int ans = 0; for (int i = N;i >= 0;i--) { if ( depth[a] < depth[b] && depth[grand[b][i]] >= depth[a] ) ans += gw[b][i] , b = grand[b][i]; } // 然后一起向上跳跃 for (int j = N; j >= 0 ; j -- ) { if ( grand[a][j] != grand[b][j] ) { ans += gw[a][j]; ans += gw[b][j]; a = grand[a][j]; b = grand[b][j]; } } // 如果最后还不相等的话 加上本身的值 if(a != b) ans += gw[a][0], ans += gw[b][0]; return ans; } int main(){ int t; cin>>t; // t组数据 while ( t -- ) { scanf("%d %d",&n,&m); for (int i = 0;i <= n;i++) G[i].clear(); int u,v,w; for ( int i = 0; i < n-1 ; i ++ ) { scanf("%d %d %d",&u,&v,&w); G[u].push_back(edge(w,v)); G[v].push_back(edge(w,u)); } init(); int a ,b ; for (int i = 1;i <= m; i ++ ) { scanf("%d %d",&a,&b); printf("%d\n",lca(a,b)); } } return 0; } ``` 下面是一些LCA的题目集合 [poj1986](http://poj.org/problem?id=1986) [hdu2874](http://acm.hdu.edu.cn/showproblem.php?pid=2874) [po3417](http://poj.org/problem?id=3417) [poj3728](http://poj.org/problem?id=3728)