1

倍增法（Doubling Method）

倍增法详细解题思路1. 概述倍增法（Binary Lifting）是一种在处理与树或图相关的问题时常用的算法技巧，特别是在计算最近公共祖先（LCA）、树上路径查询等问题中非常有用。倍增法的核心思想是通过预处理，使得在查询时能够快速地跳过多个节点，从而达到减少查询时间复杂度的目的。2. 预处理阶段2.1 深度和祖先计算

3. 查询阶段

3.1 调整深度

• 调整节点深度：将较深的节点调整到与另一个节点同一深度。通过从高位到低位的二进制位检查，逐步调整节点。

3.2 逼近最近公共祖先

• 逼近LCA：在同一深度基础上，通过倍增法逐步逼近最近公共祖先。同样从高位到低位检查，逐步调整节点。

4. 总结

倍增法通过预处理每个节点的深度和第 (2^k) 个祖先，使得在查询最近公共祖先时能够快速跳过多个节点，从而大大减少查询时间复杂度。这种方法在处理大规模树结构的查询问题时非常高效。

示例代码

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;


const int MAXN = 100005; // 最大节点数
const int LOG = 20;      // 二进制位数


vector<int> adj[MAXN];   // 邻接表存储树
int parent[MAXN][LOG];   // 存储每个节点的第2^k个祖先
int depth[MAXN];         // 存储每个节点的深度


// 深度优先搜索，预处理深度和祖先
void dfs(int node, int par, int dep) {
    depth[node] = dep;
    parent[node][0] = par;
    for (int i = 1; i < LOG; ++i) {
        if (parent[node][i-1] != -1) {
            parent[node][i] = parent[parent[node][i-1]][i-1];
        }
    }
    for (int child : adj[node]) {
        if (child != par) {
            dfs(child, node, dep + 1);
        }
    }
}


// 计算最近公共祖先
int lca(int u, int v) {
    if (depth[u] < depth[v]) swap(u, v);


    // 将u调整到与v同一深度
    for (int i = LOG - 1; i >= 0; --i) {
        if (depth[u] - (1 << i) >= depth[v]) {
            u = parent[u][i];
        }
    }


    if (u == v) return u;


    // 同时向上跳，逼近LCA
    for (int i = LOG - 1; i >= 0; --i) {
        if (parent[u][i] != parent[v][i]) {
            u = parent[u][i];
            v = parent[v][i];
        }
    }


    return parent[u][0];
}


int main() {
    int n, q;
    cin >> n >> q;


    // 读取树的边
    for (int i = 1; i < n; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }


    // 初始化parent数组
    for (int i = 0; i < MAXN; ++i) {
        for (int j = 0; j < LOG; ++j) {
            parent[i][j] = -1;
        }
    }


    // 预处理深度和祖先
    dfs(1, -1, 0);


    // 处理查询
    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << "LCA of " << u << " and " << v << " is " << lca(u, v) << endl;
    }


    return 0;
}