图解树上差分与LCA：用‘砍树’这道题彻底搞懂算法竞赛中的树上操作-开发者社区

从蓝桥杯真题"砍树"掌握树上差分与LCA的核心思想

树形结构是算法竞赛中不可或缺的重要数据结构，而树上差分与最近公共祖先(LCA)算法则是解决树形路径问题的两把利剑。本文将以蓝桥杯真题"砍树"为例，通过直观的图解和生动的比喻，带你彻底理解这两个算法的精髓。

1. 理解题目背景与基础概念

"砍树"题目描述了一个森林中有n棵树，每棵树之间有n-1条边连接。我们需要根据给定的m条路径，找到满足所有路径都经过的某条边，并将其砍掉。这看似简单的题目背后，隐藏着树形结构中的经典问题——如何高效处理路径上的统一更新与查询。

1.1 树的存储方式

在算法实现中，我们通常使用邻接表来存储树结构。邻接表的核心思想是为每个节点维护一个链表，存储与之直接相连的所有节点。这种存储方式既节省空间，又能高效地进行遍历操作。

const int N = 1e5 + 10; vector<int> edge[N]; // 邻接表存储树结构 // 添加边 void addEdge(int x, int y) { edge[x].push_back(y); edge[y].push_back(x); }

1.2 暴力解法的问题分析

最直观的解法是对每条路径进行DFS遍历，标记路径上的所有边。最后统计被标记m次的边。这种方法虽然简单，但时间复杂度高达O(m*n)，在数据量较大时完全无法接受。

// 暴力DFS解法伪代码 for 每条路径(a,b): 从a到b进行DFS遍历 路径上的每条边计数+1

2. 最近公共祖先(LCA)算法精解

LCA算法是解决树上路径问题的关键。两个节点的最近公共祖先是指树中同时是这两个节点祖先的深度最大的节点。

2.1 倍增法实现LCA

倍增法是LCA的高效实现方式之一，通过预处理每个节点向上2^k层的祖先，将查询复杂度优化到O(logn)。

int depth[N], up[N][20]; // up[i][k]表示i的2^k级祖先 // 预处理 void dfs(int u, int parent) { depth[u] = depth[parent] + 1; up[u][0] = parent; for(int k = 1; k < 20; k++) up[u][k] = up[up[u][k-1]][k-1]; for(int v : edge[u]) { if(v != parent) dfs(v, u); } } // 查询LCA int lca(int a, int b) { if(depth[a] < depth[b]) swap(a,b); // 将a提升到与b同一深度 for(int k = 19; k >= 0; k--) if(depth[a] - (1<<k) >= depth[b]) a = up[a][k]; if(a == b) return a; // 同时向上寻找 for(int k = 19; k >= 0; k--) if(up[a][k] != up[b][k]) a = up[a][k], b = up[b][k]; return up[a][0]; }

2.2 树链剖分实现LCA

另一种高效的LCA实现方式是树链剖分，它将树分解为多条链，通过跳跃链头的方式快速找到LCA。

int siz[N], dep[N], fa[N], son[N], top[N]; // 第一次DFS，计算大小、深度、重儿子 void dfs1(int u, int father) { siz[u] = 1; dep[u] = dep[father] + 1; fa[u] = father; son[u] = 0; for(int v : edge[u]) { if(v == father) continue; dfs1(v, u); siz[u] += siz[v]; if(siz[son[u]] < siz[v]) son[u] = v; } } // 第二次DFS，构建重链 void dfs2(int u, int t) { top[u] = t; if(son[u]) dfs2(son[u], t); for(int v : edge[u]) { if(v != fa[u] && v != son[u]) dfs2(v, v); } } // 查询LCA int lca(int x, int y) { while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); x = fa[top[x]]; } return dep[x] < dep[y] ? x : y; }

3. 树上差分算法详解

树上差分是一种高效处理树上路径更新的算法，它巧妙地将路径上的区间更新转化为几个端点的单点更新。

3.1 基本思想

假设我们要对树上从u到v的路径上的所有边进行+1操作，可以分解为：

u节点+1
v节点+1
LCA(u,v)节点-2

这样，后续通过一次DFS遍历累加子树和，就能得到每条边被覆盖的次数。

3.2 算法实现步骤

初始化差分数组：为每个节点创建差分值，初始为0
处理每条路径：
- w[u] += 1
- w[v] += 1
- w[lca(u,v)] -= 2
后序遍历计算子树和：通过DFS计算每个节点的子树和，这个和就是对应边上方的覆盖次数

int w[N]; // 差分数组 // 处理路径 void processPath(int a, int b) { int ancestor = lca(a,b); w[a]++; w[b]++; w[ancestor] -= 2; } // 计算子树和 void dfs_sum(int u, int father) { for(int v : edge[u]) { if(v == father) continue; dfs_sum(v, u); w[u] += w[v]; } }

3.3 为什么这样设计？

这种差分设计的精妙之处在于：

从u到根节点的路径上所有边都会受到+1影响
从v到根节点的路径上所有边也会受到+1影响
从LCA到根节点的路径被加了两次，所以需要-2来抵消
最终只有u到v路径上的边会被+1影响

4. 综合应用解决"砍树"问题

结合LCA和树上差分，我们可以高效解决"砍树"问题。以下是完整的解决方案：

4.1 算法流程

读取输入，构建树结构
预处理LCA需要的信息
对每条路径应用树上差分
计算子树和，得到每条边的覆盖次数
找出被所有路径覆盖的边中编号最大的

4.2 完整代码实现

#include<bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int N = 1e5 + 10; int n, m; int w[N]; // 差分数组 map<pii,int> id; // 边编号映射 vector<int> edge[N]; // 树链剖分变量 int siz[N], dep[N], fa[N], son[N], top[N]; // 第一次DFS void dfs1(int u, int father) { siz[u] = 1, dep[u] = dep[father] + 1; fa[u] = father, son[u] = 0; for(int v : edge[u]) { if(v == father) continue; dfs1(v, u); siz[u] += siz[v]; if(siz[son[u]] < siz[v]) son[u] = v; } } // 第二次DFS void dfs2(int u, int t) { top[u] = t; if(!son[u]) return; dfs2(son[u], t); for(int v : edge[u]) { if(v != fa[u] && v != son[u]) dfs2(v, v); } } // 查询LCA int lca(int x, int y) { while(top[x] != top[y]) { if(dep[top[x]] < dep[top[y]]) swap(x,y); x = fa[top[x]]; } return dep[x] < dep[y] ? x : y; } // 计算子树和 void cal_sum(int u, int father) { for(int v : edge[u]) { if(v == father) continue; cal_sum(v, u); w[u] += w[v]; } } void solve() { cin >> n >> m; // 建树 for(int i = 1; i < n; i++) { int x, y; cin >> x >> y; edge[x].push_back(y); edge[y].push_back(x); id[{x,y}] = id[{y,x}] = i; } // 预处理LCA dfs1(1, 0); dfs2(1, 1); // 处理每条路径 for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; w[a]++; w[b]++; w[lca(a,b)] -= 2; } // 计算子树和 cal_sum(1, 0); // 寻找答案 int ans = -1; for(int u = 2; u <= n; u++) { if(w[u] == m) { int edgeId = id[{u, fa[u]}]; ans = max(ans, edgeId); } } cout << ans << endl; } int main() { ios::sync_with_stdio(0); cin.tie(0); solve(); return 0; }

4.3 复杂度分析

时间复杂度：
- 预处理LCA：O(n)
- 处理m条路径：每条路径O(1)的差分操作 + O(1)的LCA查询
- 计算子树和：O(n)的DFS遍历
- 总复杂度：O(n + m)
空间复杂度：O(n)用于存储树结构和各种辅助数组

相比暴力解法的O(m*n)复杂度，这个解法在n和m较大时优势非常明显。

5. 算法扩展与应用场景

掌握了树上差分和LCA后，我们可以解决更多树形路径问题。以下是几个典型应用场景：

5.1 树上路径统计问题

问题类型：统计每条边/节点被多少条给定路径覆盖
解决方法：直接应用树上差分
变种：可以统计覆盖次数满足特定条件的边/节点

5.2 树上路径修改问题

问题类型：对多条路径上的边/节点进行增减操作，最后查询每个边/节点的值
解决方法：树上差分+子树求和
示例：给多条路径上的边增加权值，最后查询每条边的总权值

5.3 结合其他算法的综合应用

与树链剖分结合：处理更复杂的路径查询和修改
与线段树结合：处理动态的路径查询问题
与并查集结合：解决某些特殊的连通性问题

图解树上差分与LCA：用‘砍树’这道题彻底搞懂算法竞赛中的树上操作