树形DP与换根思想：从医院设置问题看带权重心算法

1. 项目概述从“医院设置”问题看图的中心性度量最近在辅导学生准备信息学奥赛时又翻出了这道经典题目——“医院设置”。它同时出现在《信息学奥赛一本通》的例题1338【例3-3】和洛谷P1364上足以说明其作为图论与树形结构入门题目的重要地位。表面上看这是一个关于在社区中选址建立医院使得居民看病总距离最短的问题。但它的内核实际上是一个关于如何在树结构上高效计算“带权重心”或“最小化带权距离和”的经典模型。这个问题不仅考察了对树这种数据结构的理解更是在引导我们思考如何将现实世界的优化问题抽象为可计算的图论模型。简单来说题目给你一棵树每个树节点代表一个居民点节点上有一个权值居民数量。树上的边代表道路每条边的长度通常视为1单位距离。你需要在这棵树的某个节点上可以是居民点也可以是道路上的任意点具体看题目变体设立一所医院目标是让所有居民去看病的总路程每个居民点的权值乘以该点到医院的最短距离最小。这个“总路程”就是我们要求解的最小代价。为什么这道题值得深究因为在算法竞赛中它像一把钥匙打开了“树形DP”动态规划和“换根DP”这两扇大门。许多更复杂的问题比如树的最长路径、树的直径、特定节点的最优选择等其解题思路都与此一脉相承。对于初学者搞懂这道题就意味着掌握了在树上进行系统性计算和状态转移的基本功。今天我就结合自己多年的刷题和教学经验把这个问题的几种主流解法掰开揉碎讲清楚并分享一些在实现时容易踩的“坑”。2. 核心思路解析暴力、树形DP与换根思想的演进面对这个问题最直观的想法可能就是暴力枚举。既然医院可以建在任何节点上那我就把每个节点都假设为医院选址然后分别计算以该节点为医院时所有居民的总路程最后取最小值。这个思路完全正确也是我们验证其他算法正确性的基础。对于一个有n个节点的树计算从一个源点到所有其他点的距离和使用一次深度优先搜索DFS或广度优先搜索BFS需要 O(n) 的时间复杂度。那么枚举 n 个节点总时间复杂度就是 O(n²)。当 n 在 10^3 到 10^4 量级时这个复杂度尚可接受这也是题目常见的数-据范围。暴力枚举法虽然朴素但它是理解问题本质的起点在竞赛中确保正确性的朴素算法往往比写错的“高级”算法得分更高。然而当树节点数量达到 10^5 甚至更高时O(n²) 的暴力法就力不从心了。这就需要我们寻找更优的解法。这里就引出了两种更高效的方法基于一次DFS的预处理后快速计算各点代价的“换根DP”法以及严格符合“医院可建在边上”要求的二次扫描法。它们的核心都在于利用树的无环结构通过一次或两次遍历推导出所有节点作为根时的信息避免重复计算。为什么“换根”思想如此强大想象一下我们已经花费 O(n) 时间计算出了以节点u为根医院时的总路程f[u]。现在医院选址挪到与u相邻的节点v上。那么对于整棵树来说只有连接u和v的这条边两侧的节点受到了影响。所有原本在v子树里的节点去医院的距离都减少了1因为医院从u移到了更近的v而所有不在v子树里的节点包括u和其他部分去医院的距离都增加了1。如果我们能提前知道每个节点的子树权重之和那么从f[u]推导f[v]就是一个 O(1) 的公式计算。这样我们只需要一次DFS求出以某个节点为根时的f[root]和各子树权重然后再一次DFS换根就能推出所有节点的f[i]总复杂度 O(n)。这个“换根”过程就是动态规划在树形结构上的典型应用。状态f[u]表示以u为医院的总距离和。状态转移就是当根从父节点u移动到子节点v时如何利用已知信息快速更新f[v]。理解了这个模型你就掌握了解决一大类“树形结构上对每个节点求某个全局属性”问题的钥匙。3. 关键算法细节与实现要点接下来我们深入到两种主流解法的实现细节中。我会先用“换根DP”解决医院必须建在节点上的标准版再讨论医院可以建在边上的扩展版。3.1 解法一换根DP医院建于节点这是解决洛谷 P1364 和《一本通》例题最标准、最高效的方法。我们定义几个关键数组w[i]: 节点i的居民数量权值。size[i]: 以i为根的子树中所有节点的权值之和。这是一个非常重要的中间量。f[i]: 以节点i为医院时所有居民的总距离和即我们要最小化的目标值。算法分为两个清晰的阶段第一阶段第一次DFS后序遍历计算size和初始的f[root]。我们任选一个节点作为根比如1号节点。进行一次深度优先搜索。对于当前节点u递归计算其所有子节点v的size[v]和f[v]这里f[v]是以v为根的子树内部如果医院设在v上子树内居民的距离和这是一个局部值注意区分。回溯到u时size[u] w[u] sum(size[v])即自身权值加上所有子树权值和。同时我们可以计算以u为根时仅考虑其子树内居民的总距离。但这个距离并不是我们最终定义的f[u]。更常用的方法是在第一次DFS中我们直接计算以我们选定的根节点比如1为医院时的总距离f[1]。这个计算可以在DFS过程中累加对于每条边(u, v)节点v子树中的所有居民共size[v]人去看病都需要经过这条边因此对总距离的贡献是size[v]。所以f[1] sum(size[v])其中v是所有非根节点。实际上f[root]就等于所有节点的权值 * 该节点到根节点的深度之和。我们可以在DFS求深度的同时累加得到。关键细节第一次DFS的主要目的除了求出f[root]更重要的是求出每个节点的size[i]子树权值和。这是后续换根推导的基石。第二阶段第二次DFS先序遍历即“换根”推导所有f[i]。现在我们知道了f[1]以及每个节点的size[i]。我们再进行一次DFS这次的任务是从父节点u的状态f[u]推导出子节点v的状态f[v]。 假设当前我们在节点u已知f[u]。现在考虑将医院从u移到其子节点v。对于v子树内的所有节点共size[v]个权值单位它们去医院的距离减少了1所以总距离减少size[v]。对于不在v子树内的所有节点总权值为total_weight - size[v]它们去医院的距离增加了1所以总距离增加(total_weight - size[v])。 因此状态转移方程为f[v] f[u] - size[v] (total_weight - size[v]) f[u] total_weight - 2 * size[v]其中total_weight是所有节点权值之和这是一个常量。通过这次DFS我们可以从根节点开始递推地计算出所有节点的f[i]。最后答案就是min(f[1], f[2], ..., f[n])。实现注意事项树的存储使用邻接表vectorint graph[N]来存储这棵无向树。注意输入可能是父子节点编号也可能给出的是每个节点的左右孩子类似二叉树。对于更一般的树用邻接表处理更通用。避免重复访问在DFS过程中必须传递一个parent参数防止走回头路。初始化total_weight需要在读入权值时提前计算好。数据类型总距离和可能很大f[i]和中间变量应使用long long类型。3.2 解法二二次扫描与医院建于边上的情况《信息学奥赛一本通》的例题描述中明确提到“医院可以建在居民点上也可以建在道路上”。这比洛谷 P1364默认建在点上的要求更宽泛。当医院可以建在边上时最优解有可能出现在某条边的中间某个点而不仅仅是端点。如何解决呢思路需要进一步延伸。对于一条连接u和v的边长度为L通常为1。假设我们在这条边上距离u为x的位置建医院。那么总距离函数F(x)是关于x的一个分段线性函数。可以证明在这个一维线段上使总距离最小的点x一定位于某个“权重平衡点”附近或者说最小值点会使得医院两侧的“权重压力”尽可能平衡。一个经典的二次扫描解法如下第一次扫描DFS任选根计算每个节点i的size[i]子树权值和同时计算以该节点为根的子树中所有居民到该节点的距离之和down[i]。down[i]的计算类似于树形DPdown[u] sum(down[v] size[v])因为子节点v子树内的居民到u的距离等于他们到v的距离down[v]再加上经过边(u,v)的一步共size[v]步。第二次扫描DFS换根计算每个节点i的up[i]表示不在i子树内的所有居民到节点i的距离之和。以及最终我们要求的f[i]即所有居民到i的总距离f[i] down[i] up[i]。计算up[v]v是u的子节点up[v] up[u] down[u] - (down[v] size[v]) (total_weight - size[v])。这个公式需要仔细理解up[u] down[u]是除了v子树外其他点到u的距离和减去(down[v] size[v])是为了去掉v子树对down[u]的贡献然后加上(total_weight - size[v])是因为其他所有点到v比到u多了一步。处理边上的点对于边(u, v)设其长度为1。我们已经有了f[u]和f[v]以及size[u]和size[v]注意这里的size需要根据根的选择来定义通常我们定义size[v]为以v为根的子树权值和。假设医院建在靠近u的x位置0 x 1。那么u一侧包含u及其部分子树具体取决于根的选择的居民到医院的距离变化是线性的。实际上可以证明总距离函数在这条边上是凸的最小值点要么在端点u或v要么在满足某种平衡条件的内部点。一个实用的方法是考虑将边上的点想象成将这条边细分出一个虚拟节点。最优解往往出现在“权重平衡”的位置。一个简化且正确的做法是对于每条边答案的最小值候选点就是这条边的两个端点。因为如果最优解在边内部那么将其移动到离权重更大的一侧更近的端点不会使总距离增加可以推导。因此在实际编程中我们只需要比较所有节点作为医院选址的f[i]取最小值即可。这是因为在单位边权的树上位于边内部的点一定不如某个端点优。这是一个非常重要的结论可以简化代码直接使用解法一的换根DP结果即可。实操心得很多同学在遇到“边上可建”的条件时会想复杂去求边上的精确位置。实际上对于本题的树结构和单位边权只需考虑节点。这是一个常见的思维陷阱。务必先进行数学分析或举简单例子验证避免实现复杂化。4. 代码实现与逐行解析下面我给出基于“换根DP”思路解决医院建于节点情况的C代码实现并附上详细注释。这个版本可以直接通过洛谷 P1364。#include iostream #include vector #include algorithm using namespace std; const int N 105; // 根据题目范围调整本题一般n100 typedef long long ll; vectorint graph[N]; // 邻接表存树 ll w[N]; // 节点权值居民数 ll size[N]; // 子树权值和 ll f[N]; // f[i]: 以i为医院的总距离和 ll total_weight 0; // 总权值 int n; // 第一次DFS以u为当前节点fa为父节点计算size[u]和以u为根的“子树贡献” // 同时这里我们采用另一种方式直接计算f[root]在递归过程中累加深度*权值 ll dfs1(int u, int fa, int depth) { size[u] w[u]; // 初始化包含自身权值 ll sum_dist w[u] * depth; // 当前节点对根节点总距离的贡献 for (int v : graph[u]) { if (v fa) continue; // 避免回环 sum_dist dfs1(v, u, depth 1); // 累加子树的贡献 size[u] size[v]; // 回溯时更新子树权值和 } return sum_dist; // 返回以u为根的子树中所有节点到初始根节点的距离*权值之和 } // 第二次DFS换根从u推导其子节点v的f[v] void dfs2(int u, int fa) { for (int v : graph[u]) { if (v fa) continue; // 核心换根公式 f[v] f[u] total_weight - 2 * size[v]; dfs2(v, u); } } int main() { cin n; for (int i 1; i n; i) { cin w[i]; total_weight w[i]; // 计算总权值 int left, right; cin left right; // 构建无向树图 if (left) { graph[i].push_back(left); graph[left].push_back(i); } if (right) { graph[i].push_back(right); graph[right].push_back(i); } } // 任选1号节点为根进行第一次DFS // dfs1的返回值就是以1为根时所有居民到节点1的总距离 f[1] dfs1(1, 0, 0); // 进行第二次DFS换根推导所有f[i] dfs2(1, 0); // 找出最小的总距离 ll ans f[1]; for (int i 2; i n; i) { if (f[i] ans) ans f[i]; } cout ans endl; return 0; }代码关键点解析dfs1函数参数depth记录了当前节点u到初始根节点1号的距离。sum_dist累加了当前子树中所有节点权值*深度的和这个值在根节点1的调用返回后就是f[1]。同时我们顺利求出了每个节点的size[i]。dfs2函数这是换根的核心。当我们知道f[u]后利用公式f[v] f[u] total_weight - 2 * size[v]来推导子节点v的f[v]。注意这个公式成立的前提是size[v]的定义必须是在第一次DFS中以1为根时v的子树权值和。我们的dfs1正是这样计算的。图的构建题目输入有时以“左孩子、右孩子”形式给出我们将其转化为无向图邻接表。使用vectorint graph[N]存储graph[u]包含所有与u相邻的节点。数据类型总距离可能超过int范围因此使用long long。5. 常见错误与调试技巧即便理解了算法实现时也常常会遇到各种问题。这里我总结几个最常见的“坑”将树误当作二叉树处理题目虽然样例输入像二叉树但描述是一棵普通的树。必须用邻接表来存储并用fa参数防止DFS走回头路。如果只用左右孩子指针遇到非二叉树结构就会出错。排查方法用一组简单的非二叉树的测试数据验证例如三个节点成一条线1-2-3。size数组定义混淆在换根公式f[v] f[u] total_weight - 2 * size[v]中size[v]必须是在第一次DFS确定的根如节点1下以v为根的子树权值和。如果在换根过程中size[v]发生了变化公式就不成立。我们的实现中size数组只在dfs1中计算一次之后是只读的这保证了正确性。忽略权值和的距离溢出这是最隐蔽的错误。节点权值和总距离的乘积很容易超出 32 位整数 (int) 的范围。例如100个节点每个节点权值10000距离最大为100总距离可能达到 10^8 量级还在int范围内。但如果节点数和权值更大就危险了。安全起见所有与权值、距离、总和相关的变量统一使用long long。换根公式推导错误公式f[v] f[u] total_weight - 2 * size[v]是核心。自己推导一遍是加深理解的最好方式。可以画一棵简单的树手工计算f[u]和f[v]验证公式。初始化与边界条件确保total_weight正确累加。对于孤立的节点权值为0算法也应正确处理。调试技巧实录小数据手工模拟当程序输出错误时不要急于看代码。取一个 n3 或 4 的小例子在纸上画出树标上权值手工计算出每个节点作为医院的总距离暴力枚举。然后单步调试你的程序对比每一步计算出的size[i]和f[i]是否与手工结果一致。这是定位逻辑错误最有效的方法。打印中间变量在dfs1和dfs2的关键步骤后打印出size[u],f[u]等变量。观察它们的值是否符合预期。特别是换根前后f值的变化是否满足推导公式。测试边界数据所有节点权值相同。权值集中在某一个叶子节点。链状树退化的树。n1 的情况。6. 算法扩展与思维提升掌握了“医院设置”的基础解法我们可以看看它如何延伸到更复杂的问题这有助于构建知识网络。扩展到带边权如果道路长度不是1而是不同的正整数c。公式需要调整。此时size[v]的定义不变但换根公式中的1需要替换为边权c。推导时v子树内居民距离减少c子树外居民距离增加c。公式变为f[v] f[u] - size[v] * c (total_weight - size[v]) * c f[u] c * (total_weight - 2 * size[v])。实现时需要在DFS中传递边权信息。与“树的中心”和“树的质心”关联树的中心树上到一个点最远距离最小的点。求法通常是求树的直径然后找直径中点。这与“医院设置”追求总和最小不同中心是追求最大值最小。树的质心树中删除该点后产生的最大子树节点数最小的点。求质心是树分治算法的第一步。有趣的是在所有权值为1的树上“医院设置”问题距离和最小的解往往就是树的质心或者在其附近。这是一个很好的性质将不同概念联系起来。实际问题建模这道题的本质是“设施选址问题”在树形网络上的特例。类似的现实问题很多比如在居民区设立快递柜、在电网中设立变电站、在公司分布式架构中部署中心缓存服务器等只要网络结构可以抽象为树优化目标是最小化加权距离和都可以套用这个模型。理解一道题不仅仅是AC。更重要的是理清它的算法脉络看清它背后的模型并知道它如何变化、如何与其他知识点连接。当你再遇到“树形结构上对所有节点求某个全局值”的问题时不妨想想能不能用一次DFS预处理出一些子树信息能不能用换根DP在O(n)时间内求出所有答案“医院设置”这道题正是训练这种思维能力的绝佳起点。