树形动态规划在道路修建问题中的应用

1. 题目背景与核心思路这道来自NOI2011的[道路修建]问题是典型的树形动态规划应用题。题目给出一个n个节点的树结构每条边都有修建费用要求计算所有节点两两之间路径费用之和。看似简单的题意背后考察的是选手对树结构的理解和动态规划的应用能力。我在第一次接触这道题时被其O(n)时间复杂度的要求难住了。经过反复思考和实践总结出了一套可靠的解题思路。关键在于发现对于树中的任意一条边它对总费用的贡献等于该边两侧节点数的乘积乘以边权。2. 算法设计与证明2.1 树形DP状态定义我们定义size[u]表示以u为根的子树中的节点数。对于每条边(u,v)假设v是u的子节点那么这条边的贡献就是cost w * size[v] * (n - size[v])其中w是边权n是总节点数。这个公式的直观理解是这条边会被size[v]个节点到(n-size[v])个节点的路径所经过。我在白板上画了几个例子验证这个结论确实成立。2.2 递归计算子树大小实现时采用后序遍历的方式递归计算void dfs(int u, int fa) { size[u] 1; for(auto [v, w] : G[u]) { if(v fa) continue; dfs(v, u); size[u] size[v]; ans w * size[v] * (n - size[v]); } }这里G是邻接表存储的树结构ans累加每条边的贡献。3. 实现细节与优化3.1 数据结构选择使用vector存储邻接表比传统的指针式链表更高效vectorvectorpairint, int G(n1);每个节点对应一个vector存储(相邻节点边权)对。3.2 输入处理技巧题目给出的边是无向的但建树时需要处理成有向的。一个小技巧是读入时直接建立双向边while(m--) { int u, v, w; cin u v w; G[u].emplace_back(v, w); G[v].emplace_back(u, w); }3.3 避免重复计算在dfs时需要记录父节点fa防止走回头路造成无限递归。这是树形DP的常见陷阱。4. 完整AC代码#include bits/stdc.h using namespace std; using ll long long; int main() { int n; cin n; vectorvectorpairint, int G(n1); vectorint size(n1); ll ans 0; for(int i1; in; i) { int u, v, w; cin u v w; G[u].emplace_back(v, w); G[v].emplace_back(u, w); } functionvoid(int,int) dfs [](int u, int fa) { size[u] 1; for(auto [v, w] : G[u]) { if(v fa) continue; dfs(v, u); size[u] size[v]; ans 1LL * w * size[v] * (n - size[v]); } }; dfs(1, 0); cout ans endl; return 0; }5. 复杂度分析与变种思考5.1 时间复杂度整个算法只需要一次DFS遍历时间复杂度是O(n)完全满足题目要求。5.2 空间复杂度邻接表存储需要O(n)空间递归栈深度在最坏情况下也是O(n)。5.3 题目变种如果题目改为求所有路径中最大/最小路径值思路就完全不同了。这时可能需要用到树的直径等概念。这也说明了理解题目本质的重要性。6. 调试与验证技巧6.1 小数据测试建议先用n3,4这样的小数据手工计算验证。比如3个节点成链时总费用应该是所有边权的两倍之和。6.2 中间输出可以在dfs过程中输出size数组的值确认递归计算是否正确。6.3 边界检查特别注意n1时的边界情况虽然题目保证n≥1但好的编程习惯应该处理所有可能。7. 同类题目推荐洛谷P1352 没有上司的舞会 - 基础树形DP洛谷P2015 二叉苹果树 - 树形DP背包洛谷P1273 有线电视网 - 树形分组背包这些题目都运用了类似的树形动态规划思想建议按顺序练习以巩固这个知识点。