倍增算法-最大公共祖先

难度系数：4
适用范围：入门级

“倍增”是一个用途极其广泛的算法，是由“分治、递归”算法延伸推广出的一种处理问题的极其常用的思想，可以解决如快速幂、求LCA（最近公共祖先）、O(1)求区间极值、求后缀数组……等一系列问题。

倍增法求LCA

/**************************************************************** 
 * Description: LCA implementation with binary lifting
 * Author: Alex Li
 * Date: 2023-06-12 08:36:14
 * LastEditTime: 2024-05-09 19:43:24
****************************************************************/

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int l; //树的高度的对数值，用于LCA查询。
const int MAX_SIZE=10001; //树的最大节点数，设置为10001
//MAX_DEPTH每个节点需要存储祖先的最大深度，设定为16。理论上，对于10000个节点的树，
//深度至多需要约14（因为2^14≈16384),但这里取了16作为保险。
const int MAX_DEPTH=16;  
//使用动态数组的方式存储每个节点的邻接节点列表，实现了树的图形结构。
vector<int>  graph[MAX_SIZE]; 
//存储每个节点的深度。
int depth[MAX_SIZE]; 
//存储每个节点在不同 2 的幂次的祖先。
int fathers[MAX_SIZE][MAX_DEPTH]; 


int N;//结点数

//深度优先搜索（DFS）函数，节点遍历用于构建树结构中的fathers[][]数组。
//两个参数：当前正在访问的节点 node 和该节点的父节点 father。
void DFS(int node, int father){   
    
    depth[node]=depth[father]+1; //设定当前节点的深度为父节点深度加1。
    fathers[node][0]=father; //记录当前节点的直接父节点（即2^0级祖先）。
    //建立祖先的表,fatthers[node][i]是指node结点向上第2^i层的祖先结点
    for(int i=1;i<depth[node];i++)
        fathers[node][i]=fathers[fathers[node][i-1]][i-1];
    int cnt=graph[node].size();
    //把node结点在graph表中所有结点(除父结点外)深搜遍历
    for (int i = 0; i <cnt; i++){
        if(father!=graph[node][i])
            DFS(graph[node][i],node);
    }
}

int LCA(int a, int b){
    //这里检查两个节点的深度，确保 a 是更深的节点（或者它们的深度相同）。
    if (depth[a] < depth[b]) {
        swap(a, b);
    }
    //循环是为了将节点 a 向上提升到与节点 b 同一深度。通过2^i级的跳跃来迅速减小深度差，这样可以高效地调整 a 的位置。
    for (int i = l; i >= 0; i --) {
        if (depth[a]-(1<<i) >= depth[b]) {
            a = fathers[a][i];
        }
    }
    if (a == b) return a;
    //两个结点一起向上跳，先跳大的，再跳小的。
    for (int i = l ; i >= 0; i --) {
    //如果两个结点的father一样，哪就从重跳小的，如果不一样，哪就把两个结点移动到新高度。
        if (fathers[a][i] != 0 && fathers[a][i] != fathers[b][i]) {
            a = fathers[a][i];
            b = fathers[b][i];
        }
    }
    return fathers[a][0];
}
int main(){
    int r,a,b;
    cout<<"please input the number of Node and No. of root Node: ";
    cin>>N>>r;
    //用于计算在倍增方法中所需存储每个节点的最大跳跃深度，
    l=ceil(log2(N));
    cout<<'\n';
    cout<<"input edge: "<<'\n';
    for(int i=1;i<=N-1;i++){
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    DFS(r,0); // r是根结点编号，, 根结点的父结点为0
    cout<<"please input two node which you want to know LCA: ";
    cin>>a>>b;
    cout<<"the LCA of "<<a<<" and "<<b<<" is "<<LCA(a,b);
}

up[u][i] = up[up[u][i-1]][i-1]

公式的含义：

up[u][i] 表示节点 u 的第 2ⁱ个祖先。
up[u][i-1] 表示节点 u 的第 2ⁱ⁻¹个祖先。
up[up[u][i-1]][i-1] 表示节点 u 的第 2ⁱ⁻¹ 个祖先的第 2ⁱ⁻¹个祖先。

换句话说，节点 u 的第 2ⁱ 个祖先，可以通过先找到节点 u 的第 2ⁱ⁻¹ 个祖先，然后再找这个祖先的第 2ⁱ⁻¹个祖先来得到。

为什么这个公式成立？

这个公式的核心思想是倍增。我们通过将跳跃的步长翻倍（2ⁱ）来快速找到祖先。

基础情况：
- 当 i=0 时，up[u][0] 表示节点 u 的第 2⁰=1 个祖先，也就是它的直接父节点。
- 这是已知的，可以通过 DFS 遍历树时直接记录。
递推情况：
- 假设我们已经计算了所有节点的第 2ⁱ⁻¹ 个祖先（即 up[u][i-1]）。
- 那么节点 u 的第 2ⁱ个祖先，就是节点 u 的第 2ⁱ⁻¹ 个祖先的第 2ⁱ⁻¹个祖先。
- 这是因为 2ⁱ=2ⁱ⁻¹+2ⁱ⁻¹，即跳跃 2ⁱ步相当于先跳跃 2ⁱ⁻¹ 步，再跳跃 2ⁱ⁻¹ 步。

for (int i = LOG - 1; i >= 0; --i) {
    if (up[u][i] != up[v][i]) {
    u = up[u][i];
    v = up[v][i];
    }
}
 return up[u][0];

代码的作用：

前提条件：
- 在这段代码执行之前，u 和 v 已经被提升到同一深度。
- 现在需要找到 u 和 v 的最近公共祖先。
从大到小尝试跳跃：
- i 从 LOG - 1 开始，逐步减小到 0。
- 每次循环尝试跳跃 2i2i 步。
跳跃的条件：
- 如果 up[u][i] != up[v][i]，说明 u 和 v 的第 2i2i 个祖先 不是同一个节点。
- 这意味着它们的最近公共祖先还在更高的位置，因此可以安全地将 u 和 v 同时向上跳跃 2i2i 步。
跳跃的结果：
- 通过 u = up[u][i] 和 v = up[v][i]，将 u 和 v 同时向上跳跃 2i2i 步。
- 这样，u 和 v 会逐渐靠近它们的最近公共祖先。
终止条件：
- 当 up[u][i] == up[v][i] 时，说明当前跳跃的步长 2i2i 太大了，会导致跳过最近公共祖先。
- 因此，不进行跳跃，继续尝试更小的步长。
最终结果：
- 当循环结束时，u 和 v 会位于它们的最近公共祖先的 直接子节点 位置。
- 因此，up[u][0] 或 up[v][0] 就是它们的最近公共祖先。

简写代码：

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

const int MAXN = 100005; // 最大节点数
const int LOG = 20;      // log2(MAXN)

vector<int> tree[MAXN];  // 树的邻接表表示
int up[MAXN][LOG];       // up[i][j] 表示节点 i 的第 2^j 个祖先
int depth[MAXN];         // 节点的深度

// DFS 预处理，计算每个节点的深度和倍增表
void dfs(int u, int parent) {
    up[u][0] = parent;  // u 的第 2^0 个祖先是 parent
    for (int i = 1; i < LOG; ++i) {
        up[u][i] = up[up[u][i-1]][i-1];  // 递推计算 u 的第 2^i 个祖先
    }
    for (int v : tree[u]) {
        if (v != parent) {
            depth[v] = depth[u] + 1;  // 计算子节点的深度
            dfs(v, u);
        }
    }
}

// 查找节点 u 的第 k 个祖先
int getKthAncestor(int u, int k) {
    for (int i = 0; i < LOG; ++i) {
        if (k & (1 << i)) {
            u = up[u][i];
        }
    }
    return u;
}

// 查找两个节点的最近公共祖先
int lca(int u, int v) {
    // 确保 u 是较深的节点
    if (depth[u] < depth[v]) {
        swap(u, v);
    }
    // 将 u 提升到与 v 同一深度
    u = getKthAncestor(u, depth[u] - depth[v]);
    if (u == v) {
        return u;
    }
    // 同时提升 u 和 v，直到它们的祖先相同
    for (int i = LOG - 1; i >= 0; --i) {
        if (up[u][i] != up[v][i]) {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

int main() {
    int n; // 节点数
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        tree[u].push_back(v);
        tree[v].push_back(u);
    }
    dfs(1, -1);  // 假设根节点是 1，且没有父节点（-1）
    int q; // 查询次数
    cin >> q;
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << "LCA of " << u << " and " << v << " is " << lca(u, v) << endl;
    }
    return 0;
}

P3379

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

倍增算法-最大公共祖先

公式的含义：

为什么这个公式成立？

代码的作用：