当前位置：首页 > news >正文

基于c++的LCA倍增法实现

news 来源：原创 2025/6/8 19:09:39

原理就不写了，自己找b站视频学习

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

const int MAXN = 100005; // 最大节点数
const int MAXLOG = 20; // 最大对数深度

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

// DFS预处理每个节点的深度和父节点信息
void dfs(int u, int p) {
parent[u][0] = p; // 直接父节点
for (int i = 1; i < MAXLOG; ++i) {
parent[u][i] = parent[parent[u][i-1]][i-1];
}

for (int v : tree[u]) {
if (v != p) {
depth[v] = depth[u] + 1;
dfs(v, u);
}
}
}

// 初始化，从根节点开始预处理
void init(int root, int n) {
depth[root] = 0;
dfs(root, -1); // 根节点的父节点设为-1
}

// 查询u和v的LCA
int lca(int u, int v) {
// 确保u是较深的节点
if (depth[u] < depth[v]) {
swap(u, v);
}

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

// 如果此时u和v相同，则v就是LCA
if (u == v) {
return u;
}

// 同时提升u和v直到它们的父节点相同
for (int i = MAXLOG - 1; i >= 0; --i) {
if (parent[u][i] != -1 && parent[u][i] != parent[v][i]) {
u = parent[u][i];
v = parent[v][i];
}
}

// 返回LCA
return parent[u][0];
}

int main() {
int n; // 节点数
cin >> n;

// 构建树
for (int i = 0; i < n - 1; ++i) {
int u, v;
cin >> u >> v;
tree[u].push_back(v);
tree[v].push_back(u);
}

int root = 1; // 假设根节点是1
init(root, n);

// 查询示例
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;
}

解释DFS遍历部分的代码

这段代码是深度优先搜索（DFS）遍历树的递归实现部分，用于预处理每个节点的深度和倍增祖先信息。让我详细解释一下：

cpp

复制

下载

for (int v : tree[u]) {if (v != p) {depth[v] = depth[u] + 1;dfs(v, u);}
}

代码分解：

for (int v : tree[u]):
- 这是一个范围for循环，遍历节点u的所有邻接节点v
- tree[u]是存储节点u所有子节点的容器（通常是vector）
if (v != p):
- 检查当前邻接节点v是否不是父节点p（避免回溯到父节点）
- 这是树遍历的关键，确保我们不会无限循环（因为树是无向图，但遍历时要当作有向图处理）
depth[v] = depth[u] + 1:
- 设置子节点v的深度为父节点u的深度+1
- 这样递归计算所有节点的深度
dfs(v, u):
- 递归调用DFS，处理子节点v
- 这里u作为v的父节点传入下一层递归

下面再解释解释这段代码

for (int i = MAXLOG - 1; i >= 0; --i) {if (depth[u] - (1 << i) >= depth[v]) {u = parent[u][i];}
}

代码分解：

for (int i = MAXLOG - 1; i >= 0; --i):
- 从最大的可能步长开始尝试（MAXLOG-1），逐步减小到0
- 这是倍增法的典型模式：先尝试大跨度跳跃，再逐步细化
1 << i:
- 这是位运算，表示2的i次方（即2^i）
- 例如：1<<3 = 8，1<<0 = 1
- 这里表示尝试向上跳跃2^i个层级
depth[u] - (1 << i) >= depth[v]:
- 检查如果u向上跳2^i层后，深度是否仍然不小于v的深度
- 确保跳跃后不会"跳过"目标深度
u = parent[u][i]:
- 如果条件满足，将u更新为其2^i级祖先
- 这是实际执行跳跃的操作

为什么这样工作？

倍增法的核心思想是：任何整数都可以表示为2的幂次的和。例如：

5 = 4 + 1
7 = 4 + 2 + 1
10 = 8 + 2

从最大的可能步长开始尝试，可以确保：

每次跳跃都是尽可能大的安全步长
总能在O(logN)时间内完成调整

示例说明：

假设：

depth[u] = 10, depth[v] = 5
MAXLOG = 5 (最大能表示2^4=16层跳跃)

循环执行过程：

i=4: 尝试跳16层 → 10-16 <5 → 不跳
i=3: 尝试跳8层 → 10-8=2 <5 → 不跳
i=2: 尝试跳4层 → 10-4=6 ≥5 → 跳，u=parent[u][2], depth=6
i=1: 尝试跳2层 → 6-2=4 <5 → 不跳
i=0: 尝试跳1层 → 6-1=5 ≥5 → 跳，u=parent[u][0], depth=5

最终u的深度从10调整到5，与v同深度。

关键点：

1<<i实现了高效的2^i计算
从大到小的尝试顺序确保跳跃效率
这种方法的时间复杂度是O(logN)，N是树的高度

这段代码是LCA算法中调整节点深度的关键部分，体现了倍增法的精髓。

解释DFS遍历部分的代码

代码分解：

代码分解：

为什么这样工作？

示例说明：

关键点：

相关文章：