树上边差分算法详解

1. 什么是树上边差分树上边差分是一种在树形数据结构如树、森林上高效处理路径修改与单点查询问题的算法技巧。它通过将路径上的边权修改操作转化为对树上少数几个节点的标记操作从而将时间复杂度从 O(n) 降低到 O(1)单次操作最终通过一次深度优先搜索DFS完成所有标记的传递与汇总。其核心思想借鉴自一维数组的差分思想并将其巧妙地推广到了树结构上。2. 算法原理2.1 问题模型给定一棵有 n 个节点的树每条边有一个初始权值通常为 0。现在需要支持以下两种操作路径修改给定树上两个节点 u 和 v以及一个值 c将节点 u 到节点 v 的简单路径上的每一条边的权值都增加 c。单边查询查询某条边 (x, y) 的当前权值。树上边差分的目标就是高效地处理大量的路径修改操作最后再一次性回答所有边的最终权值。2.2 差分数组的类比在一维数组中若要对区间 [l, r] 的所有元素加上 c我们可以使用差分数组 diff[]diff[l] c; diff[r1] - c;最后对 diff 数组求前缀和即可得到原数组每个位置被增加的总值。树上边差分是这一思想在树上的延伸。2.3 树上边差分的操作设树上每个节点 i 有一个差分值 diff[i]初始为 0。定义树根为 root通常为 1。对于一次路径修改操作 (u, v, c)找到 u 和 v 的最近公共祖先LCA记为 lca。进行以下四次标记diff[u] c; diff[v] c; diff[lca] - 2 * c;注意如果树根 root 的父节点不存在通常不对其进行操作。有些实现中若 lca 恰好是 root则只进行 diff[u] c 和 diff[v] c。2.4 权值汇总DFS在所有修改操作完成后从根节点 root 开始进行一次深度优先搜索DFS。对于当前节点 u 和其子节点 v对应边 u-v在 DFS 回溯时将子节点 v 的 diff 值累加到父节点 u 的 diff 值上diff[u] diff[v]; // 在遍历完子节点v后执行DFS 结束后对于任意一条边 (u, v)假设 u 是 v 的父节点该边最终的权值就等于节点 v 的 diff 值。原理节点 v 的 diff 值实质上代表了所有覆盖了边 (u, v) 的路径修改操作的 c 值之和。3. 算法流程与示例3.1 算法步骤预处理通过 DFS 获取每个节点的深度、父节点等信息并预处理 LCA例如使用倍增法或 Tarjan 算法。处理修改对于每个路径修改 (u, v, c)计算 lca LCA(u, v)然后执行diff[u] c; diff[v] c; diff[lca] - 2 * c;权值下传进行第二次 DFS或第一次 DFS 的回溯阶段将子节点的 diff 值累加到父节点。void dfs2(int u, int fa) { for (int v : tree[u]) { if (v fa) continue; dfs2(v, u); diff[u] diff[v]; // 回溯时累加 } }获取答案对于边 (u, v)u 是 v 的父节点其最终权值 diff[v]。3.2 示例演示考虑一棵 5 个节点的树边初始权值为 01 / \ 2 3 / \ 4 5执行两次操作将路径 4-2-1-3 上所有边 1。即 u4, v3, c1, lca1将路径 5-2 上所有边 2。即 u5, v2, c2, lca2操作后的 diff 标记为操作1: diff[4]1, diff[3]1, diff[1]-2操作2: diff[5]2, diff[2]2, diff[2]-4 因为 lca2汇总后各节点 diff 初始值为diff[1]-2, diff[2]-2, diff[3]1, diff[4]1, diff[5]2。执行 DFS 权值下传假设 1 为根遍历节点 2diff[2] diff[4] diff[5] -2 1 2 1遍历节点 1diff[1] diff[2] diff[3] -2 1 1 0最终边权子节点 diff 值边(1,2): diff[2] 1边(1,3): diff[3] 1边(2,4): diff[4] 1边(2,5): diff[5] 2经验证符合操作要求。4. 代码实现C#include iostream #include vector #include cmath using namespace std; const int MAXN 100005; const int LOG 17; // log2(MAXN) vectorint tree[MAXN]; int depth[MAXN]; int parent[MAXN][LOG]; long long diff[MAXN]; // 差分数组 // 预处理深度和倍增祖先 void dfs1(int u, int fa) { depth[u] depth[fa] 1; parent[u][0] fa; for (int i 1; i LOG; i) { parent[u][i] parent[parent[u][i-1]][i-1]; } for (int v : tree[u]) { if (v fa) continue; dfs1(v, u); } } // 计算 LCA 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[parent[u][i]] depth[v]) { u parent[u][i]; } } if (u v) return u; // 一起向上跳 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]; } // 处理路径修改 void pathAdd(int u, int v, int c) { int p lca(u, v); diff[u] c; diff[v] c; diff[p] - 2 * c; // 如果考虑对 lca 的父边也有影响点差分思想则需要额外处理。 // 对于纯边差分上述操作已足够。 } // 第二次 DFS累加差分值 void dfs2(int u, int fa) { for (int v : tree[u]) { if (v fa) continue; dfs2(v, u); diff[u] diff[v]; } } int main() { int n, m; cin n m; // n 个节点m 次操作 // 建树 for (int i 1; i n; i) { int u, v; cin u v; tree[u].push_back(v); tree[v].push_back(u); } // 预处理 LCA depth[0] -1; dfs1(1, 0); // 假设 1 为根节点 // 处理 m 次路径加操作 for (int i 0; i m; i) { int u, v, c; cin u v c; pathAdd(u, v, c); } // 权值下传 dfs2(1, 0); // 输出每条边的最终权值按输入顺序或任意顺序 // 假设边 (u, v) 中 u 是 v 的父节点则边权为 diff[v] // 实际输出需要根据建树时记录的父子关系进行 cout Edge values (child nodes diff): endl; for (int i 2; i n; i) { // 根节点 1 没有父边 cout edge ( parent[i][0] , i ) diff[i] endl; } return 0; }5. 树上边差分 vs 树上点差分两者常被混淆但针对的问题不同特性树上边差分树上点差分修改对象路径上的边路径上的点包括端点查询对象单边权值单点权值核心操作diff[u] c; diff[v] c; diff[lca] - 2*c;diff[u] c; diff[v] c; diff[lca] - c; diff[parent[lca]] - c;权值汇总子节点 diff 累加到父节点子节点 diff 累加到父节点最终答案边 (u,v) 权值 diff[子节点]点 u 权值 diff[u]简单记忆边差分在 lca 处减 2c点差分在 lca 处减 c 并在其父节点再减 c。6. 典型应用场景网络流量统计树形网络中的链路流量增加。树上路径染色将路径上的边标记某种颜色最后询问每条边的颜色计数。资源分配在树形权限结构中从某个节点到另一个节点路径上的通道分配资源。算法竞赛如 NOIP、ICPC 中常见的“树上路径加、单边查询”问题。7. 总结树上边差分是一种非常高效的离线处理树上路径修改的技巧。其核心步骤可以概括为标记利用 LCA将路径修改转化为对 u, v, lca 三个节点的 O(1) 标记。下传通过一次 DFS 回溯将子节点的标记累加到父节点。取值每条边的最终权值等于其较深端点子节点的 diff 值。掌握该算法需要同时理解一维差分思想、树的 DFS 序与父子关系以及 LCA 的求法。它与树上点差分是姊妹技巧应根据问题需求灵活选用。