树形动态规划解析：洛谷P2052道路修建问题

发布时间：2026/10/27 16:04:57

1. 题目背景与核心问题解析

洛谷P2052 [NOI2011] 道路修建是一道经典的树形动态规划问题，考察选手对树结构的理解和动态规划的应用能力。题目描述了一个国家需要修建道路系统，每条道路都有修建费用，要求计算在保证任意两个城市连通的前提下，所有可能修建方案中"不平衡值"的最小值。

这个"不平衡值"的定义非常关键：对于某条道路，假设它连接的两个区域城市数量分别为A和B，那么这条道路的贡献值为|A-B|*道路修建费用。整个方案的不平衡值就是所有道路贡献值的总和。

注意：题目中隐含的树结构特性非常重要。因为题目保证任意两个城市间只有唯一通路，所以整个道路系统实际上构成了一棵树。

1.1 题目输入输出分析

输入格式：

第一行：整数N表示城市数量
接下来N-1行：每行三个整数u,v,w，表示城市u和v之间可以修建一条费用为w的道路

输出格式：

一个整数表示最小的不平衡值总和

示例输入：

3 1 2 1 1 3 2

示例输出：

2. 解题思路与算法设计

2.1 树形DP基本思路

这道题的核心在于理解树的结构和动态规划的状态转移。我们需要计算每条边对总不平衡值的贡献，这取决于该边两侧子树的大小。

基本思路如下：

将整个树结构建立起来
对树进行后序遍历（DFS）
对于每个节点，计算其子树的大小
对于每条边(u,v)，计算|size[v] - (N-size[v])| * w，其中size[v]是以v为根的子树的大小

2.2 关键状态定义

定义size[u]表示以u为根的子树中包含的节点数量。这个值可以通过递归地累加所有子节点的size值得到。

对于每条边(u,v)，假设v是u的子节点，那么这条边的贡献值为：abs(size[v] - (N - size[v])) * w

2.3 算法实现步骤

建图：使用邻接表存储树结构
DFS遍历：从根节点（通常选1号节点）开始进行深度优先搜索
计算子树大小：在回溯过程中累加子树大小
计算贡献值：对于每条边，根据子树大小差计算其贡献
累加总不平衡值

3. 代码实现与详细解析

3.1 C++完整代码实现

#include <iostream> #include <vector> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 1e6 + 5; struct Edge { int to, w; }; vector<Edge> G[MAXN]; long long res = 0; int N, size[MAXN]; void dfs(int u, int fa) { size[u] = 1; for (auto &e : G[u]) { int v = e.to, w = e.w; if (v == fa) continue; dfs(v, u); size[u] += size[v]; res += (long long)abs(size[v] - (N - size[v])) * w; } } int main() { cin >> N; for (int i = 1; i < N; ++i) { int u, v, w; cin >> u >> v >> w; G[u].push_back({v, w}); G[v].push_back({u, w}); } dfs(1, -1); cout << res << endl; return 0; }

3.2 代码关键点解析

邻接表存储：使用vector数组G来存储树结构，每个节点对应一个vector，存储其相邻节点和边权。
DFS设计：
- 参数u表示当前节点，fa表示父节点（防止回溯）
- 初始化size[u] = 1（包含自己）
- 遍历所有子节点，递归计算子树大小
贡献值计算：
- size[v]表示以v为根的子树大小
- N - size[v]表示另一侧的节点数量
- 绝对值差乘以边权即为该边的贡献
数据类型选择：
- 使用long long存储结果，防止大数溢出
- size数组使用int足够，因为N最大1e6

4. 算法优化与注意事项

4.1 时间复杂度分析

建图：O(N)
DFS遍历：O(N)
总时间复杂度：O(N)

这个复杂度对于N=1e6的数据量是完全可行的。

4.2 空间复杂度分析

邻接表存储：O(N)
size数组：O(N)
递归栈空间：最坏O(N)（当树退化成链时）

4.3 常见错误与调试技巧

栈溢出问题：
- 对于N=1e6，递归深度可能过大导致栈溢出
- 解决方法：使用非递归DFS或手动扩栈
- 扩栈代码（在C++中）：
```
#pragma comment(linker, "/STACK:1024000000,1024000000")
```
整数溢出问题：
- 中间计算结果可能超过int范围
- 必须使用long long存储结果
根节点选择：
- 理论上选择任意节点作为根都可以
- 通常选择1号节点为根
边的双向处理：
- 建图时记得添加双向边
- DFS时注意判断父节点防止回溯