1. 引言在树形数据结构如树、图的算法问题中高效处理路径查询、子树修改等操作是常见的挑战。树上点分治和树上点差分是两种强大且互补的技术它们分别从“分而治之”和“前缀和思想”的角度为解决树上问题提供了优雅的解决方案。本文将深入探讨这两种算法的核心思想、实现细节、应用场景以及它们之间的联系与区别。2. 树上点分治2.1 核心思想树上点分治Tree Centroid Decomposition借鉴了序列分治的思想通过递归地选取树的重心作为分割点将原树分解为若干个规模更小的子树从而将问题规模对数级降低。重心树中一个节点删除它后得到的每棵子树的大小不超过原树大小的一半。分治过程找到当前树的重心。处理所有经过该重心的路径这是算法的核心计算部分。删除重心递归处理得到的各个连通块子树。2.2 算法步骤与实现以下是一个典型的树上点分治框架以统计路径长度等于 K 的路径数量为例#include bits/stdc.h using namespace std; const int N 1e5 5; vectorpairint, 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. 收集从重心出发的所有路径长度 vectorint 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; vectorint 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. 结语树上点分治和树上点差分是树形结构算法中两个非常重要的范式。点分治以其“重心分解”的思想为解决树上路径统计问题提供了通用框架而点差分则利用“差分前缀和”的思想将路径修改的复杂度大幅降低。掌握这两种算法并能根据问题特征灵活选用或结合是解决许多树上难题的关键。建议读者通过上述例题进行代码实现以加深理解。