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

树上差分算法解析与砍树问题实战

news 2026/8/10 5:37:54

1. 问题背景与算法选型

最近在刷AcWing题库时遇到了4963题"砍树"，这是一道典型的树结构问题。题目大意是给定一棵树和若干条路径，要求找出满足特定条件的边。这类问题在实际应用中很常见，比如网络路由优化、社交网络分析等场景。

经过分析，这道题的核心在于高效统计每条边被多少条路径覆盖。直接暴力遍历每条路径显然时间复杂度太高（O(nm)），对于大规模数据无法承受。这时候就需要引入树上差分算法，特别是边差分技术。

树上差分本质是利用前缀和思想在树结构上进行高效区间操作。相比点差分，边差分在处理边相关问题时更加直观。

2. 算法原理深度解析

2.1 边差分的基本思想

边差分的关键在于如何将路径操作转化为对端点的修改。对于树上的边(u,v)，我们可以：

任选一个根节点（通常选1号节点）
定义diff数组记录差分值
对于路径a→b：
- diff[a] += 1
- diff[b] += 1
- diff[lca(a,b)] -= 2

这样处理后，通过后序遍历累加子树差分值，就能得到每条边被覆盖的次数。

2.2 LCA的快速计算

实现边差分需要快速求解最近公共祖先(LCA)。常见方法有：

倍增法：预处理每个节点的2^k级祖先
Tarjan离线算法
树链剖分

以倍增法为例，预处理时间复杂度O(nlogn)，单次查询O(logn)。核心预处理代码如下：

void dfs(int u, int father) { depth[u] = depth[father] + 1; fa[u][0] = father; for(int i=1; i<=LOG; i++) fa[u][i] = fa[fa[u][i-1]][i-1]; for(int v : g[u]) { if(v == father) continue; dfs(v, u); } }

3. 完整实现步骤

3.1 数据结构准备

首先需要建立树的邻接表表示，同时记录边的编号：

vector<pair<int,int>> g[N]; // g[u] = {v, edge_id} int edge_id[N]; // 记录父边编号

3.2 DFS预处理

进行深度优先遍历，同时完成三件事：

计算节点深度
预处理倍增数组
记录父边编号

void dfs_pre(int u, int father) { depth[u] = depth[father] + 1; fa[u][0] = father; for(int i=1; i<=LOG; i++) fa[u][i] = fa[fa[u][i-1]][i-1]; for(auto [v, id] : g[u]) { if(v == father) continue; edge_id[v] = id; // 记录v的父边编号 dfs_pre(v, u); } }

3.3 LCA查询实现

基于预处理好的倍增数组，实现LCA查询：

int lca(int a, int b) { if(depth[a] < depth[b]) swap(a,b); for(int k=LOG; k>=0; k--) if(depth[fa[a][k]] >= depth[b]) a = fa[a][k]; if(a == b) return a; for(int k=LOG; k>=0; k--) if(fa[a][k] != fa[b][k]) a=fa[a][k], b=fa[b][k]; return fa[a][0]; }

3.4 差分操作与统计

处理所有查询路径，进行差分操作：

void apply_diff(int a, int b) { int p = lca(a,b); diff[a]++; diff[b]++; diff[p] -= 2; }

最后通过后序遍历统计每条边的实际覆盖次数：

void dfs_sum(int u, int father) { for(auto [v, id] : g[u]) { if(v == father) continue; dfs_sum(v, u); sum[id] = diff[v]; // 记录边id的覆盖次数 diff[u] += diff[v]; } }