一, 首先回顾一下什么是倍增算法, 倍增算法就是改善一下一步一步跳的缓慢, 改为跳 2^k 步从而达到加快速度的目的, 倍增算法一般要先预处理一个数组, 代表从从某个点开始跳 2^k 个数到达哪里, 比如 ST 表的 ST[i][j] 代表从第 i 个数向后 2^j 个数, 树上倍增求 LCA 的 f[i][j] 表示 i 的第 2^j 个祖先是谁.
二, 最近公共祖先 LCA 概念篇
1, 祖先: 与 x 处于同一条重链且深度小于点 x 的节点都成为点想的祖先.
2, 公共祖先: 若给定一棵树, 结点 z 即是结点 x 的祖先, 结点 z 也是结点 y 的祖先, 那么称 z 是结点 x 和 y 的公共祖先.
3, 最近公共祖先: 结点 x 和结点 y 的所有祖先中深度最深的那个, 记作 LCA(x,y).
比如在此图中, 5 的祖先有 1 和 2; 5 和 6 的公共祖先有 1 和 2; 5 和 6 的最近公共祖先是 2; 有没有发现根节点是所有任意两个节点的公共祖先,
所以最近公共祖先一定存在, 最差是根节点.
三, 如何求解 LCA
1, 考虑如何暴力求解, 如果两个结点的深度相同, 我们是不是只需要让两个结点同时一步一步往上走, 即 a 走到它的父亲的同时, b 也走到它的父亲, 如果两个点走到的结点不相同就证明当前节点不是 a 和 b 的最近公共祖先就继续走, 知道走到节点相同证明当前节点是点 a 和点 b 的最近公共祖先.
2, 考虑如何优化 1,1 缓慢的原因是它在一步一步的向上走所以导致了算法的低效, 如果我们可以大步向上走, 每次在不超过范围的情况下向上走 2^k 步再判断是不是就加快了算法速度, 为了实现这个效果我们引入倍增算法
首先要预处理两个数组 Log(以 2 为底的对数中整数最大的那个),Log[0]=-1,Log[i]=Log[i>>1]|1;F(i, j) 表示点 i 向上走 2j 步的结点, Fi,0 就是点 i 的父亲节点, F(i, j)= F((Fi, j−1), j−1)(从第 i 个点向上走 2^j 个点肯定等于从 i 出发向上走 2^(j-1) 个点再向上走 2^(j-1) 个节点.
算法流程:
将 a 和 b 调整到相同高度
a. 判断 a 和 b 是否重合, 若重合则该点即为答案
b. 令 a 和 b 一起向上移动尽可能大的距离, 保证移动后两点不重合
c. 此时两点的父亲结点即为答案
- #include<cstdio>
- #include<iostream>
- #include<cstring>
- #include<algorithm>
- #define maxn 500005
- using namespace std;
- struct node
- {
- int ed,nxt;
- };
- node edge[maxn<<1];
- int first[maxn],n,m,s,cnt,f[maxn][30],Log[maxn],dep[maxn];
- inline void add_edge(int s,int e)
- {
- cnt++;
- edge[cnt].ed=e;
- edge[cnt].nxt=first[s];
- first[s]=cnt;
- return;
- }
- inline void deal_first(int k,int fa)
- {
- dep[k]=dep[fa]+1;
- f[k][0]=fa;
- for(int i=1;(1<<i)<=dep[k];i++)
- f[k][i]=f[f[k][i-1]][i-1];
- for(int i=first[k];i;i=edge[i].nxt)
- {
- int e=edge[i].ed;
- if(e==fa) continue;
- deal_first(e,k);
- }
- }
- inline int Lca(int a,int b)
- {
- if(dep[a]<dep[b]) swap(a,b);
- for(int i=Log[dep[a]];i>=0;i--)
- if(dep[f[a][i]]>=dep[b]) a=f[a][i];
- if(a==b) return a;
- for(int k=Log[dep[a]];k>=0;k--)
- if(f[a][k]!=f[b][k])
- a=f[a][k],b=f[b][k];
- return f[a][0];
- }
- int main()
- {
- scanf("%d%d%d",&n,&m,&s);
- for(int i=1;i<=n-1;i++)
- {
- int s,e;
- scanf("%d%d",&s,&e);
- add_edge(s,e);
- add_edge(e,s);
- }
- dep[s]=1;
- deal_first(s,0);
- Log[0]=-1;
- for(int i=1;i<=n;i++)
- Log[i]=Log[i>>1]+1;
- for(int i=1;i<=m;i++)
- {
- int a,b;
- scanf("%d%d",&a,&b);
- printf("%d\n",Lca(a,b));
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3169748.html