１.倍增是什么？ 请看我的另一篇文章 ＲＭＱ ２.什么是LCA？ Least Common Ancestors：顾名思义，最近并且公共的祖先，如下图Ｈ和Ｍ的LCA是Ｅ。 （这个算法我也是看了好久，才有点顿悟） 思路：这个算法暴力就是从最底部一点一点向上跳，但这样是非常耗时的。而采取倍增来做，就减少了跳的步数。利用一个二维数组f[ i ][ j ]而他表示的是从i，向上跳2^j个单位，其中通过递归来更新初始化 f 数组，而其中就利用了动态规划，f[ i ][ j ] = f[ f[i][j -1]][j -1],这可以这样理解，从i向上跳 2^j 个单位 = 从i先跳 2^(j-1)单位，然后再跳 2^(j-1) 个单位，就相当于 2^j = 2^(j-1) + 2^(j-1) 下面代码一洛谷一道经典的模板题作为样例：洛谷LCA
#include <bits/stdc++.h> using namespace std; const int maxn = 5e5+10; int tot,n,m,s,to[2*maxn],head[2*maxn],next[2*maxn]; int f[maxn][30],d[maxn]; void add(int x,int y){ //链式前向星存储 to[++tot] = y;next[tot] = head[x]; head[x] = tot; } void dfs(int u,int fa){ d[u] = d[fa]+1; //每递归一层，深度就要加一。 for(int i = 1; (1<<i) <= d[u]; i++) f[u][i] = f[f[u][i-1]][i-1]; //动态转移方程， for(int i = head[u]; i ; i = next[i]){ int v = to[i]; if(v == fa)continue; //只递归他的儿子节点，遇到父亲节点直接跳过，因为是无向图 f[v][0] = u; //f[v][0]表示从v向上跳2^0 = 1，也就是他的父节点 dfs(v,u); } } int LCA(int a,int b){ if(d[a] < d[b]) swap(a,b); //强制定义a比b深度更深 for(int i = 20; i >= 0; i--){ //在这里有三种做法，我感觉还是这种好理解 if(d[f[a][i]] >= d[b]) a = f[a][i]; //先将a跳到b的高度 if(a == b) return a; //如果两个相等说明较高的b就是a与b的LCA } for(int i = 20; i >= 0; i--) if(f[a][i] != f[b][i]) //找到最后一个不相等的，那么他们中任意一个就是他们的LCA a = f[a][i],b = f[b][i]; return f[a][0]; //也可以return f[b][0]; } int main(){ scanf("%d%d%d",&n,&m,&s); for(int i = 1; i <= (n-1); i++){ int x,y; scanf("%d%d",&x,&y); add(x,y); add(y,x); //无向图 } dfs(s,0); while(m--){ int a,b; scanf("%d%d",&a,&b); printf("%d\n",LCA(a,b)); } return 0; }第二个处理跳到相同高度的方法：x = fa[x][lg[depth[x]-depth[y]] - 1];
#include <bits/stdc++.h> using namespace std; const int maxn = 1e5+10; struct zzz { int t, nex; }e[maxn << 1]; int head[maxn], tot; void add(int x, int y) { e[++tot].t = y; e[tot].nex = head[x]; head[x] = tot; } int depth[maxn], fa[maxn][22], lg[maxn]; void dfs(int now, int fath) { //now表示当前节点，fath表示它的父亲节点 fa[now][0] = fath; depth[now] = depth[fath] + 1; for(int i = 1; i <= lg[depth[now]]; ++i) fa[now][i] = fa[fa[now][i-1]][i-1]; //这个转移可以说是算法的核心之一 //意思是now的2^i祖先等于now的2^(i-1)祖先的2^(i-1)祖先，2^i = 2^(i-1) + 2^(i-1) for(int i = head[now]; i; i = e[i].nex) if(e[i].t != fath) dfs(e[i].t, now); } int LCA(int x, int y) { if(depth[x] < depth[y]) //用数学语言来说就是：不妨设x的深度 >= y的深度 swap(x, y); while(depth[x] > depth[y]) x = fa[x][lg[depth[x]-depth[y]] - 1]; //先跳到同一深度 if(x == y) //如果x是y的祖先，那他们的LCA肯定就是x了 return x; for(int k = lg[depth[x]] - 1; k >= 0; --k) //不断向上跳（lg就是之前说的常数优化） if(fa[x][k] != fa[y][k]) //因为我们要跳到它们LCA的下面一层，所以它们肯定不相等，如果不相等就跳过去。 x = fa[x][k], y = fa[y][k]; return fa[x][0]; //返回父节点 } int main() { int n, m, s; scanf("%d%d%d", &n, &m, &s); for(int i = 1; i <= n-1; ++i) { int x, y; scanf("%d%d", &x, &y); add(x, y); add(y, x); } for(int i = 1; i <= n; ++i) //预先算出log_2(i)+1的值，用的时候直接调用就可以了 lg[i] = lg[i-1] + (1 << lg[i-1] == i); //看不懂的可以手推一下 dfs(s, 0); for(int i = 1; i <= m; ++i) { int x, y; scanf("%d%d",&x, &y); printf("%d\n", LCA(x, y)); } return 0; }第三个处理跳到相同高度的方法：u = f[u][LG2[lowbit(d)]],d -= lowbit(d);
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 500010; struct gra{ //链式前向星 int head[maxn],to[maxn<<1],nxt[maxn<<1],cnt; void add(int a,int b){ nxt[++cnt] = head[a]; head[a] = cnt; to[cnt] = b; } void clear(int n){ fill(head, head+1+n, 0),cnt = 0; } }; const int LOG = 19; int n,m,s; struct LCA:public gra{ int f[maxn][LOG],dep[maxn],LG2[maxn]; void init(){ dep[s] = 1,dfs(s); for(int i = 0; i <= LOG-1; i++)LG2[(1<<i)] = i; } void dfs(int x){ for(int i = 1; i <= LOG-1; i++){ f[x][i] = f[f[x][i-1]][i-1]; } for(int i = head[x]; i ; i = nxt[i]){ int u = to[i]; if(u==f[x][0])continue; f[u][0] = x,dep[u] = dep[x] + 1; dfs(u); } } inline int lowbit(int x){return -x&x;} int lca(int u,int v){ if(u == v) return u; if(dep[v] > dep[u])swap(u,v); int d = dep[u] - dep[v]; while(d) u = f[u][LG2[lowbit(d)]],d -= lowbit(d); //这里和树状数组那里很像。 if(u == v) return u; for(int i = LOG-1; i >= 0; i--){ if(f[u][i]!=f[v][i]){ u = f[u][i],v = f[v][i]; } } return f[u][0]; } }wk; int main(){ scanf("%d%d%d",&n,&m,&s); for(int i = 1, u, v; i < n; i++){ scanf("%d%d",&u,&v); wk.add(u,v),wk.add(v,u); } wk.init(); for(int i = 1, u, v; i <= m; i++){ scanf("%d%d",&u,&v); printf("%d\n",wk.lca(u,v)); } return 0; }