倍增法求Lca(最近公共祖先)

原博客：https://blog.csdn.net/wjh2622075127/article/details/81060586#%E4%B8%80-%E6%98%8E%E7%A1%AE%E9%97%AE%E9%A2%98

一. 明确问题
看标题便知道了, 这篇博客力求解决的问题是求出一棵树的两个结点的最近公共祖先(LCA), 方法是倍增法.

那么什么是Lca呢?

它是一棵树上两个结点向上移动, 最后交汇的第一个结点, 也就是说这两个结点祖先里离树根最远也是离他们最近的结点.

什么是倍增法呢?

此问题说的是用倍增法求解lca问题, 那么我们可以推测这种方法还可以解决其他的一些问题(不在当下讨论范围). 在学习的过程中, 我是这么理解的: 它是一种类似于二分的方法, 不过这里不是二分, 而是倍增, 以2倍, 4倍, 等等倍数增长

一下没有理解倍增法没关系, 看后面的做法, 再结合前面, 前后贯通大概可以理解的七七八八.

二. 思路引导
下面的思路试图把过程模块化, 如果你不知道一个地方如何实现, 还请不要纠结(比如不要纠结于树的深度怎么求, 假设我们求好了树的深度)

我们找的是任意两个结点的最近公共祖先, 那么我们可以考虑这么两种种情况:

1、两结点的深度相同.

2、两结点深度不同.

算法实现来说, 第一种情况是第二种情况的特殊情况, 第二种情况是要转化成第一种情况的

先不考虑其他, 我们思考这么一个问题: 对于两个深度不同的结点, 把深度更深的那个向其父节点迭代, 直到这个迭代结点和另一个结点深度相同, 那么这两个深度相同的结点的Lca也就是原两个结点的Lca. 因此第二种情况转化成第一种情况来求解Lca是可行的.

现在还不知道如何把两个结点迭代到相同深度, 别急, 这里用到的是上面提到的倍增法.

那么剩下的问题事就解决第一种情况了, 两个结点深度相同了. 怎么求他们的Lca呢?

这里也是用了倍增法. 思路和上一步的倍增法是一样的, 不同之处有两点
1. 这次是两个结点一起迭代向前的.
2. 这次迭代停止的条件和上次不一样.

OK, 现在无法理解上面的几个过程没关系,只要知道我们用递增法解决了上述的两个问题. 具体细节看下面分析.

三. 整体框架.
那么过了一遍上面的思路引导之后, 我们可以大概想一想怎么实现整个的问题了.

其实用求Lca这个问题可以分为两块: 预处理 + 查询, 其中预处理是O(VlogV), 而一次查询是O(logV), V代表结点数量. 所以总时间复杂度为O(VlogV +ＱlogV). Q为查询次数

其步骤是这样的:
1. 存储一棵树(邻接表法)
2. 获取树各结点的上的深度(dfs或bfs)
3. 获取2次幂祖先的结点, 用parents[maxn][20]数组存储, 倍增法关键
4. 用倍增法查询Lca

步骤一
用邻接表存储一棵树, 并用from[]数组记录各结点的父节点, 其中没有父节点的就是root.

parents[u][]数组存储的是u结点的祖先结点.
如parents[u][0], 是u结点的2⁰祖先结点, 即1祖先, 也即父节点. 在输入过程中可以直接得到.
parents[u][1], 是u结点的2¹祖先结点,即2祖先, 也即父亲的父亲
parents[u][2], 是u结点的2²祖先结点, 即4祖先, 也即(父亲的父亲)的(父亲的父亲), 也就是爷爷的爷爷.

理解这个关系很重要, 这也是通过父亲结点获取整个祖先结点的关键. 现在可以先跳过.

 1 void getData(){
 2     cin >> n;
 3     int u,v;
 4     for (int i=1;i<n;i++){   //n个顶点有n-1条边
 5         cin >> u >> v;
 6         G[u].push_back(v);
 7         parents[v][0] = u;
 8         from[v] = 1;
 9     }
10     for (int i=1;i<=n;i++){ //遍历所有点找到root
11         if (from[i] == -1)
12             root = i;
13     }
14 }

步骤二

获取各结点的深度, 可以用DFS或这BFS方法

 1 void GetDepth(int u){
 2     int len = G[u].size();
 3     for (int i=0;i<len;i++){
 4         int v = G[u][i];
 5         depth[v] = depth[u]+1;
 6         getDepth(v);
 7     }
 8 }
 9 
10 
11 void GetDepth(int u){
12     queue<int> q;
13     q.push(u);
14     while (!q.empty()){
15         int v = q.front();
16         q.pop();
17         for (int i=0;i<G[v].size();i++){
18             depth[G[v][i]] = depth[v] + 1;
19             q.push(G[v][i]);
20         }
21     }
22     
23 }

步骤三
求祖先

在步骤一里面我们讨论了parents数组的意义, 它存的是结点u的2次幂祖先, 从父亲结点开始. 为什么要存2次幂? 这就是倍增法的思想了, 我们进行范围缩小不是一步一步的, 那样太暴力了, 所以我们需要某个跨度, 让我们能够先跨越大步, 接近的时候在小步小步跨越, 这样可以大大节省时间.

读者可能会疑惑, 先大步, 后小步, 可是我怎么知道什么时候该大步, 什么时候该小步呢? 难道不会不小心跨过头吗?

其实不会的, 在代码实现上, 这样的跨越有条件约束, 是非常讲究的. 读者不必为此纠结, 不过要讲解也是十分费力不讨好的事情, 所以请读者认证推敲后面Lca函数的代码, 认真琢磨为什么是那样跨越, 其中真味自会品出. 最好是自己写几个例子, 模拟跨越的过程, 在结合现实意义去理解

那么我们回到当前问题. 请看下面这个公式:

parents[i][j] = parents[parents[i][j-1]][j-1]

这是构造此数组的公式. 不难理解, 父亲的父亲就是爷爷, 爷爷的爷爷就是4倍祖先. 请读者结合现实意义去理解.

1 void getParents(){
2     for (int up=1;(1<<up)<=n;up++){
3         for (int i=1;i<=n;i++){
4             parents[i][up] = parents[parents[i][up - 1]][up - 1];
5         }
6     }
7 }

步骤四

做完了前面O(VlogV)的预处理操作, 剩下的就是查询了, 一次查询O(logV)

因此, 我们可以敏锐的想到: Lca算法适合查询次数比较多的情况, 不然, 光是预处理就花了那么多时间了. 所以说, 查询是我们享受成果的时候了.

 1 int Lca(int u, int v)
 2 {
 3     if (depth[u] < depth[v]) swap(u, v); // 使满足u深度更大, 便于后面操作 
 4     int i = -1, j;
 5     // i求的是最大二分跨度 
 6     while ((1 << (i + 1)) <= depth[u]) ++i;
 7 
 8     // 下面这个循环是为了让u和v到同一深度 
 9     for (j = i; j >= 0; --j) {
10         if (depth[u] - (1 << j) >= depth[v]) { // 是>=, 因为如果<,代表跳过头了,跳到了上面. 
11             u = parents[u][j];
12         }
13     }
14 
15     if (u == v) return u; // 刚好是祖宗 
16 
17     // u和v一起二分找祖宗
18     for (j = i; j >= 0; --j) {
19         if (parents[u][j] != parents[v][j]) {
20             u = parents[u][j];
21             v = parents[v][j];
22         }
23     }
24     return parents[u][0]; // 说明上个循环迭代到了Lca的子结点 
25 }

完整代码：（这个只适合有向图！！！）

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <cstring>
  4 #include <queue>
  5 #include <vector>
  6 using namespace std;
  7 
  8 const int maxn = 10005;
  9 int parents[maxn][20], depth[maxn];
 10 int n, from[maxn], root = -1;
 11 vector<int> G[maxn];
 12 
 13 void init()
 14 {
 15     memset(parents, 0, sizeof(parents));
 16     memset(from, -1, sizeof(from));
 17     memset(depth, -1, sizeof(depth));
 18 }
 19 
 20 void getData()
 21 {
 22     cin >> n;
 23     int u, v;
 24     for (int i = 1; i < n; ++i) {
 25         cin >> u >> v;
 26         G[u].push_back(v);
 27         parents[v][0] = u;
 28         from[v] = 1;
 29     }
 30     for (int i = 1; i <= n; ++i) {
 31         if (from[i] == -1) root = i;
 32     }
 33 }
 34 
 35 void getDepth_dfs(int u)
 36 {
 37     int len = G[u].size();
 38     for (int i = 0; i < len; ++i) {
 39         int v = G[u][i];
 40         depth[v] = depth[u] + 1;
 41         getDepth_dfs(v);
 42     }
 43 }
 44 
 45 void getDepth_bfs(int u)
 46 {
 47     queue<int> Q;
 48     Q.push(u);
 49     while (!Q.empty()) {
 50         int v = Q.front();
 51         Q.pop();
 52         for (int i = 0; i < G[v].size(); ++i) {
 53             depth[G[v][i]] = depth[v] + 1;
 54             Q.push(G[v][i]);
 55         }
 56     }
 57 }
 58 
 59 void getParents()
 60 {
 61     for (int up = 1; (1 << up) <= n; ++up) {
 62         for (int i = 1; i <= n; ++i) {
 63             parents[i][up] = parents[parents[i][up - 1]][up - 1];
 64         }
 65     }
 66 }
 67 
 68 int Lca(int u, int v)
 69 {
 70     if (depth[u] < depth[v]) swap(u, v);
 71     int i = -1, j;
 72     while ((1 << (i + 1)) <= depth[u]) ++i;
 73     for (j = i; j >= 0; --j) {
 74         if (depth[u] - (1 << j) >= depth[v]) {
 75             u = parents[u][j];
 76         }
 77     }
 78     if (u == v) return u;
 79     for (j = i; j >= 0; --j) {
 80         if (parents[u][j] != parents[v][j]) {
 81             u = parents[u][j];
 82             v = parents[v][j];
 83         }
 84     }
 85     return parents[u][0];
 86 }
 87 
 88 void questions()
 89 {
 90     int q, u, v;
 91     cin >> q;
 92     for (int i = 0; i < q; ++i) {
 93         cin >> u >> v;
 94         int ans = Lca(u, v);
 95         cout << ans << endl;
 96         //cout << u << " 和 " << v << " 的最近公共祖先(LCA)是: " << ans << endl; 
 97     }
 98 }
 99 
100 int main()
101 {
102     init();
103     getData();
104     depth[root] = 1;
105     getDepth_dfs(root);
106     //getDepth_bfs(root);
107     getParents();
108     questions();
109 }
110 /*
111 9
112 1 2
113 1 3
114 1 4
115 2 5
116 2 6
117 3 7
118 6 8
119 7 9
120 5
121 1 3
122 5 6
123 8 9
124 8 4
125 5 8
126 */

适合无向图：

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 struct yyy{
 5     int t,nex;
 6 }e[2*500001];
 7 int depth[500001],fa[500001][22],lg[500001],head[500001];
 8 int tot;
 9 void add(int x,int y) //邻接表存树
10 {
11     e[++tot].t=y;
12     e[tot].nex=head[x];
13     head[x]=tot;
14 }
15 void dfs(int f,int fath)
16 {
17     depth[f]=depth[fath]+1;
18     fa[f][0]=fath;
19     for(int i=1;(1<<i)<=depth[f];i++)
20         fa[f][i]=fa[fa[f][i-1]][i-1];
21     for(int i=head[f];i;i=e[i].nex)
22         if(e[i].t!=fath)
23             dfs(e[i].t,f);
24 }
25 int lca(int x,int y)
26 {
27     if(depth[x]<depth[y])
28         swap(x,y);
29     while(depth[x]>depth[y])
30         x=fa[x][lg[depth[x]-depth[y]]-1];
31     if(x==y)
32         return x;
33     for(int k=lg[depth[x]]-1;k>=0;k--)
34         if(fa[x][k]!=fa[y][k])
35             x=fa[x][k], y=fa[y][k];
36     return fa[x][0];
37 }
38 int n,m,s;
39 int main()
40 {
41     scanf("%d%d%d",&n,&m,&s);
42     for(int i=1;i<=n-1;i++)
43     {
44         int x,y;  scanf("%d%d",&x,&y);
45         add(x,y); add(y,x);
46     }
47     dfs(s,0);
48 
49     for(int i=1;i<=n;i++)
50         lg[i]=lg[i-1]+(1<<lg[i-1]==i);
51     for(int i=1;i<=m;i++)
52     {
53         int x,y;  scanf("%d%d",&x,&y);
54         printf("%d\n",lca(x,y));
55     }
56     return 0;
57 }