1. 引言
在树形数据结构（如树、图）的算法问题中，高效处理路径查询、子树修改等操作是常见的挑战。树上点分治和树上点差分是两种强大且互补的技术，它们分别从“分而治之”和“前缀和思想”的角度，为解决树上问题提供了优雅的解决方案。本文将深入探讨这两种算法的核心思想、实现细节、应用场景以及它们之间的联系与区别。
2. 树上点分治
2.1 核心思想
树上点分治（Tree Centroid Decomposition）借鉴了序列分治的思想，通过递归地选取树的重心作为分割点，将原树分解为若干个规模更小的子树，从而将问题规模对数级降低。
- 重心：树中一个节点，删除它后，得到的每棵子树的大小不超过原树大小的一半。
- 分治过程：
- 找到当前树的重心。
- 处理所有经过该重心的路径（这是算法的核心计算部分）。
- 删除重心，递归处理得到的各个连通块（子树）。
2.2 算法步骤与实现
以下是一个典型的树上点分治框架（以统计路径长度等于 K 的路径数量为例）：
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; vector<pair<int, int>> g[N]; // 邻接表，存储 (邻居, 边权) bool vis[N]; // 标记已删除的重心 int sz[N], maxSubtree[N]; // 子树大小，最大子树大小 // 1. 计算子树大小 void dfsSize(int u, int fa) { sz[u] = 1; maxSubtree[u] = 0; for (auto &[v, w] : g[u]) { if (v == fa || vis[v]) continue; dfsSize(v, u); sz[u] += sz[v]; maxSubtree[u] = max(maxSubtree[u], sz[v]); } } // 2. 寻找重心 int findCentroid(int u, int fa, int total) { for (auto &[v, w] : g[u]) { if (v == fa || vis[v]) continue; if (sz[v] * 2 > total) return findCentroid(v, u, total); } return u; } // 3. 收集从重心出发的所有路径长度 vector<int> distances; void collectDist(int u, int fa, int dist) { distances.push_back(dist); for (auto &[v, w] : g[u]) { if (v == fa || vis[v]) continue; collectDist(v, u, dist + w); } } // 4. 计算经过当前重心的合法路径数 int countPaths(int u, int initDist, int K) { distances.clear(); collectDist(u, -1, initDist); sort(distances.begin(), distances.end()); int l = 0, r = distances.size() - 1, cnt = 0; while (l < r) { int sum = distances[l] + distances[r]; if (sum == K) { // 处理相等情况，避免重复计数 if (distances[l] == distances[r]) { cnt += (r - l + 1) * (r - l) / 2; break; } int cntL = 1, cntR = 1; while (l + 1 < r && distances[l] == distances[l + 1]) cntL++, l++; while (r - 1 > l && distances[r] == distances[r - 1]) cntR++, r--; cnt += cntL * cntR; l++, r--; } else if (sum < K) l++; else r--; } return cnt; } // 5. 点分治主函数 int solve(int u, int K) { dfsSize(u, -1); int centroid = findCentroid(u, -1, sz[u]); vis[centroid] = true; int ans = countPaths(centroid, 0, K); // 统计经过重心的路径 // 递归处理子树 for (auto &[v, w] : g[centroid]) { if (vis[v]) continue; // 减去同一子树内产生的非法路径（两端点在同一子树） ans -= countPaths(v, w, K); ans += solve(v, K); } return ans; }2.3 时间复杂度分析
由于每次选取重心能将树平衡分割，递归深度为O(log N)。每一层中，所有子树的大小之和为O(N)，若处理经过重心的路径复杂度为O(T)，则总时间复杂度为O(T * N log N)。在上面的例子中，T为排序的O(N log N)，因此总复杂度为O(N log² N)。
2.4 典型应用
- 统计树上满足特定条件的路径数量（如长度等于 K、长度 ≤ K、路径点权满足某种性质）。
- 查询树上是否存在某条路径。
- 树上的动态规划问题（结合数据结构如线段树、平衡树）。
3. 树上点差分
3.1 核心思想
树上点差分（Tree Point Difference）是序列差分思想在树上的推广。它主要用于高效处理树上路径的区间修改和单点（或子树）查询问题。
核心操作：对树上的一条路径u -> v上的所有节点进行同一种修改（如点权增加某个值）。利用差分数组和 LCA（最近公共祖先），可以将路径修改转化为对少数几个点的修改，最后通过一次 DFS 求得每个点的实际值。
3.2 算法原理与公式
设原树节点权值数组为val[]，差分数组为diff[]。定义diff[u]表示节点u的权值与其所有子节点权值之和的差值（一种定义方式）。另一种更常用的、便于路径修改的定义如下：
对于一次路径点权更新操作：将路径u -> v上的每个节点的权值都+c。
- 设
lca = LCA(u, v)，par[lca]为lca的父节点（若存在）。 - 执行以下四次差分数组的更新：
diff[u] += cdiff[v] += cdiff[lca] -= c- 如果
par[lca]存在，则diff[par[lca]] -= c
- 所有更新操作完成后，对树进行一次 DFS（后序遍历），每个节点的实际权值
val[x] = diff[x] + Σ val[child]。
原理：这四次操作保证了增量c只对路径u -> v上的节点生效。因为差分在 LCA 处被减了一次，在 LCA 的父节点处又减了一次（如果存在），从而将影响限制在路径上。
3.3 算法实现
以下代码展示了如何使用树上点差分处理多次路径增加操作，并最终查询每个节点的权值。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5, LOG = 17; vector<int> g[N]; int depth[N], parent[N][LOG]; int diff[N], val[N]; // diff为差分数组，val为最终权值 // 预处理LCA void dfsLCA(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 : g[u]) { if (v == fa) continue; dfsLCA(v, u); } } int LCA(int u, int v) { if (depth[u] < depth[v]) swap(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]; } // 执行一次路径点权更新：u->v 路径上所有节点权值 +c void pathUpdate(int u, int v, int c) { int lca = LCA(u, v); diff[u] += c; diff[v] += c; diff[lca] -= c; if (parent[lca][0] != 0) { // 如果lca不是根节点 diff[parent[lca][0]] -= c; } } // 通过DFS计算最终每个节点的权值 void dfsCompute(int u, int fa) { val[u] = diff[u]; for (int v : g[u]) { if (v == fa) continue; dfsCompute(v, u); val[u] += val[v]; // 子节点的权值累加到父节点 } } int main() { int n, m; // n个节点，m次操作 cin >> n >> m; for (int i = 1; i < n; i++) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } dfsLCA(1, 0); // 假设1为根节点 while (m--) { int u, v, c; cin >> u >> v >> c; pathUpdate(u, v, c); } dfsCompute(1, 0); // 从根开始计算最终权值 // 输出每个节点的最终权值 for (int i = 1; i <= n; i++) { cout << val[i] << " "; } return 0; }3.4 时间复杂度与扩展
时间复杂度：预处理 LCAO(N log N)，每次路径更新O(log N)（LCA查询），最终计算权值O(N)。非常适合处理大量路径修改、最终统一查询的场景。
扩展：
- 边上差分：若修改对象是边权，定义
diff[u]表示节点 u 到其父节点边的权值变化。路径u->v修改时，操作变为diff[u]+=c, diff[v]+=c, diff[lca]-=2*c。 - 结合树状数组/线段树：如果需要支持修改和查询交错进行，可以将差分数组用树状数组维护，并结合 DFS 序将子树查询转化为区间查询。
4. 对比与总结
| 特性 | 树上点分治 | 树上点差分 |
|---|---|---|
| 核心思想 | 分治，递归选取重心分解问题 | 差分，将路径修改转化为对少数点的修改 |
| 主要操作 | 查询、统计路径 | 修改路径、查询点/子树 |
| 典型问题 | “有多少条路径满足条件？” | “对若干路径进行修改，最后每个点的值是多少？” |
| 时间复杂度 | 通常 O(N log² N) 或 O(N log N) | 修改 O(log N)，查询 O(1) 或 O(log N) |
| 优势 | 能处理复杂的路径统计和存在性问题 | 高效处理批量路径更新，实现简单 |
| 劣势 | 实现相对复杂，常数较大 | 通常只支持离线或最终统一查询 |
| 联系 | 在解决某些复杂问题时可以结合使用。例如，用点分治划分问题后，子问题内可能需要用树上差分来快速处理路径信息。 | |
5. 实战例题与思路
5.1 点分治例题：Tree (POJ 1741)
题意：给定一棵带权树，问有多少对节点之间的路径长度不超过 K。
思路：经典点分治应用。在每一层重心，计算所有从重心出发的路径长度，排序后使用双指针统计长度和 ≤ K 的路径对数，并减去同一子树内产生的非法路径。
5.2 点差分例题：JLOI2014 松鼠的新家
题意：松鼠按顺序访问一系列房间（树上节点），每到一个房间（除最后一个）都需要在该房间放糖果。求每个房间最终有多少糖果。
思路：访问序列构成了若干条路径。对于每条路径u -> v，对路径上所有节点权值 +1（注意终点重复计算的处理）。这正是树上点差分的经典应用。
6. 结语
树上点分治和树上点差分是树形结构算法中两个非常重要的范式。点分治以其“重心分解”的思想，为解决树上路径统计问题提供了通用框架；而点差分则利用“差分前缀和”的思想，将路径修改的复杂度大幅降低。掌握这两种算法，并能根据问题特征灵活选用或结合，是解决许多树上难题的关键。建议读者通过上述例题进行代码实现，以加深理解。
