企业官网建设流程全解析

1. 什么是树上边差分

树上边差分是一种在树形数据结构（如树、森林）上，高效处理路径修改与单点查询问题的算法技巧。它通过将路径上的边权修改操作，转化为对树上少数几个节点的标记操作，从而将时间复杂度从 O(n) 降低到 O(1)（单次操作），最终通过一次深度优先搜索（DFS）完成所有标记的传递与汇总。

其核心思想借鉴自一维数组的差分思想，并将其巧妙地推广到了树结构上。

2. 算法原理

2.1 问题模型

给定一棵有 n 个节点的树，每条边有一个初始权值（通常为 0）。现在需要支持以下两种操作：

1. 路径修改：给定树上两个节点 u 和 v，以及一个值 c，将节点 u 到节点 v 的简单路径上的每一条边的权值都增加 c。
2. 单边查询：查询某条边 (x, y) 的当前权值。

树上边差分的目标就是高效地处理大量的路径修改操作，最后再一次性回答所有边的最终权值。

2.2 差分数组的类比

在一维数组中，若要对区间 [l, r] 的所有元素加上 c，我们可以使用差分数组 diff[]：

diff[l] += c; diff[r+1] -= c;

最后对 diff 数组求前缀和，即可得到原数组每个位置被增加的总值。树上边差分是这一思想在树上的延伸。

2.3 树上边差分的操作

设树上每个节点 i 有一个差分值 diff[i]，初始为 0。定义树根为 root（通常为 1）。

对于一次路径修改操作 (u, v, c)：

1. 找到 u 和 v 的最近公共祖先（LCA），记为 lca。
2. 进行以下四次标记：

   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 算法步骤

1. 预处理：通过 DFS 获取每个节点的深度、父节点等信息，并预处理 LCA（例如使用倍增法或 Tarjan 算法）。
2. 处理修改：对于每个路径修改 (u, v, c)，计算 lca = LCA(u, v)，然后执行：

   diff[u] += c; diff[v] += c; diff[lca] -= 2 * c;

3. 权值下传：进行第二次 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]; // 回溯时累加 } }

4. 获取答案：对于边 (u, v)（u 是 v 的父节点），其最终权值 = diff[v]。

3.2 示例演示

考虑一棵 5 个节点的树，边初始权值为 0：

1 / \ 2 3 / \ 4 5

执行两次操作：

1. 将路径 4-2-1-3 上所有边 +1。（即 u=4, v=3, c=1, lca=1）
2. 将路径 5-2 上所有边 +2。（即 u=5, v=2, c=2, lca=2）

操作后的 diff 标记为：

• 操作1: diff[4]+=1, diff[3]+=1, diff[1]-=2
• 操作2: diff[5]+=2, diff[2]+=2, diff[2]-=4 （因为 lca=2）

汇总后各节点 diff 初始值为：diff[1]=-2, diff[2]=-2, diff[3]=1, diff[4]=1, diff[5]=2。

执行 DFS 权值下传（假设 1 为根）：

• 遍历节点 2：diff[2] += diff[4] + diff[5] = -2 + 1 + 2 = 1
• 遍历节点 1：diff[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) vector<int> 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 node's diff):" << endl; for (int i = 2; i <= n; i++) { // 根节点 1 没有父边 cout << "edge (" << parent[i][0] << ", " << i << ") = " << diff[i] << endl; } return 0; }

5. 树上边差分 vs 树上点差分

两者常被混淆，但针对的问题不同：

简单记忆：边差分在 lca 处减 2c，点差分在 lca 处减 c 并在其父节点再减 c。

6. 典型应用场景

• 网络流量统计：树形网络中的链路流量增加。
• 树上路径染色：将路径上的边标记某种颜色，最后询问每条边的颜色计数。
• 资源分配：在树形权限结构中，从某个节点到另一个节点路径上的通道分配资源。
• 算法竞赛：如 NOIP、ICPC 中常见的“树上路径加、单边查询”问题。

7. 总结

树上边差分是一种非常高效的离线处理树上路径修改的技巧。其核心步骤可以概括为：

1. 标记：利用 LCA，将路径修改转化为对 u, v, lca 三个节点的 O(1) 标记。
2. 下传：通过一次 DFS 回溯，将子节点的标记累加到父节点。
3. 取值：每条边的最终权值等于其较深端点（子节点）的 diff 值。

掌握该算法，需要同时理解一维差分思想、树的 DFS 序与父子关系，以及 LCA 的求法。它与树上点差分是姊妹技巧，应根据问题需求灵活选用。