企业官网建设流程全解析

做算法竞赛刷题的人，大概率都在洛谷上遇过P1364这道“医院设置”。题面不复杂：给一棵二叉树，每个节点住着若干居民，挑一个节点建医院，让所有人到医院的路程总和最小。这道题我刷过两遍，第一遍用Floyd莽过去的，第二遍才真正把树形DP和换根的思想吃透。说实话，n≤100的约束让这题几乎什么写法都能AC，但“能过”和“理解”是两码事——它背后藏的是带权树重心模型，恰好能把最短路、BFS、树形DP三条知识线串在一起。这篇文章就把这条线完整捋一遍，适合正在备战算法竞赛、刚啃完二叉树基础、想在树上DP上找一个经典切口的人。

1. 题目在问什么：把“医院选址”翻译成数学模型

1.1 从题面到二叉树：三个关键信息的提取

先别急着写代码，把题面的信息拆开。P1364的输入结构非常固定：第一行是节点数n，接下来n行，每行给三个整数，分别是当前节点的居民数、左孩子编号、右孩子编号，孩子编号为0表示没有。

这三个信息对应三种图论元素：

• 节点上的居民数，是点权；
• 左孩子、右孩子构成的边，是树边，题目明确每条边距离是1；
• 要建的医院，可以放在任意一个节点上，包括居民数为0的节点。

很多人第一次做这题，盯着“二叉树”三个字就开始递归建树，然后从根往下搜索，算完就往右孩子、左孩子递归，最后提交发现样例都过不了。问题就出在他把“医院只能往子树方向走”了，实际上人可以从孩子走到父亲，也可以从父亲走到孩子的孩子，整棵树是连通的，所有节点之间都可达。

所以第一步建模结论是：这不是一棵“有根二叉树”的问题，而是一棵无向树上求带权最优点的问题。这个认知转换是整道题的分水岭。

1.2 目标函数的数学意义与“距离”的陷阱

如果医院设在点v，总代价的数学表达是：

S(v) = Σ( w[u] × dist(u, v) )

其中w[u]是u节点的居民数，dist(u,v)是u到v经过的边数。注意是“边数”，不是“经过的节点数”。这个细节虽然小，但写DFS累加时特别容易多算或少算一个单位。从u到v如果经过三条边，距离就是3，居民数乘以3，这就是u点对总费用的贡献。

来看个具体例子。假设一棵链状的树：1号点有10个人，2号点有5个人，1到2是连着的。医院建在2号点，总费用就是10×1 + 5×0 = 10；如果医院建在1号点，费用是10×0 + 5×1 = 5。同样是两个节点，换个位置就差了5。这说明居民权重和距离是相乘的关系，而不是简单比较两边人数。

另一个陷阱是：居民数为0的节点也能当医院。比如一个三节点链，两端的点各住100人，中间点没人，那最优解一定在中间点。如果写代码时把“没人的点”跳过了，反而可能错过正确答案。

1.3 n≤100这个约束到底在暗示什么

n≤100是故意的。这个范围意味着：

• O(n³)的Floyd全源最短路，100³ = 100万次运算，完全能过；
• O(n²)的枚举+BFS，每个点跑一次全树BFS，也完全能过；
• O(n)的换根DP，更是随便过。

所以这题本质上是一道“怎么都能AC，但你得知道自己在做什么”的题目。我的建议是：先写一个最不容易出错的暴力版本拿分，再用正解对拍验证，而不是一上来就写DP，写完了都不知道对不对。

数据范围小的题有一个好处——非常适合用来验证思路。等哪一天碰到n=10⁵的带权重心题，就知道当时在P1364上把原理啃透是多值得的一件事。

2. 先别急着优化：三种拿分写法的复杂度与代码量

2.1 写法一：枚举医院，BFS跑全树（O(n²)）

这是最符合直觉的写法：把每个点都假设成医院，用BFS从医院出发，把整棵树搜一遍，边搜边累加“当前点的居民数 × 到医院的距离”。

但这里有个绕不开的建模问题：题目只给了左右孩子，BFS怎么从某个节点出发走到它的父节点？答案是读入的时候就别按“二叉树结构”存，而是存成无向邻接表。

#include <bits/stdc++.h> using namespace std; const int N = 105; int w[N]; vector<int> g[N]; int bfs(int s) { vector<int> dist(N, -1); queue<int> q; dist[s] = 0; q.push(s); int res = 0; while (!q.empty()) { int u = q.front(); q.pop(); for (int v : g[u]) { if (dist[v] != -1) continue; dist[v] = dist[u] + 1; res += w[v] * dist[v]; q.push(v); } } return res; } int main() { int n; cin >> n; for (int i = 1; i <= n; i++) { int l, r; cin >> w[i] >> l >> r; if (l) { g[i].push_back(l); g[l].push_back(i); } if (r) { g[i].push_back(r); g[r].push_back(i); } } int ans = INT_MAX; for (int i = 1; i <= n; i++) ans = min(ans, bfs(i)); cout << ans << endl; return 0; }

这段代码有一个容易被忽略的地方：dist[s] = 0之后，进入BFS主体之前，医院所在点s自己的居民数贡献是0，所以BFS里没有额外加w[s] * 0，这是对的。然后从s开始逐层扩展，每个新节点的距离是上一个节点距离+1，贡献是w[v] * dist[v]。复杂度是n次BFS，每次O(n)，总共O(n²)，n=100时大约一万次边访问，飞快。

2.2 写法二：Floyd全源最短路 + 枚举（O(n³)）

如果你觉得BFS还要写队列、判重，不够省心，那Floyd就是最无脑的方案。思路分三步：

1. 初始化dist[i][i] = 0，其他为无穷大；
2. 左右孩子存在时，把dist[i][l] = dist[l][i] = 1，右孩子同理；
3. 三重循环跑Floyd，得到任意两点间的距离；
4. 枚举所有节点当医院，算Σ(w[i] * dist[i][j])，取最小值。

#include <bits/stdc++.h> using namespace std; const int N = 105; const int INF = 0x3f3f3f3f; int w[N], d[N][N]; int main() { int n; cin >> n; memset(d, 0x3f, sizeof(d)); for (int i = 1; i <= n; i++) d[i][i] = 0; for (int i = 1; i <= n; i++) { int l, r; cin >> w[i] >> l >> r; if (l) d[i][l] = d[l][i] = 1; if (r) d[i][r] = d[r][i] = 1; } for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j]; int ans = INF; for (int j = 1; j <= n; j++) { int sum = 0; for (int i = 1; i <= n; i++) sum += w[i] * d[i][j]; ans = min(ans, sum); } cout << ans << endl; return 0; }

Floyd写起来最容易，但它的启发性最低——它把树当成普通图来处理，完全没有利用树的祖先关系。不过作为对拍用例的基准实现，它是称职的。

2.3 三种暴力的选择逻辑

这里把三种方法摆在一起看：

我在比赛里如果碰到带权重心题，第一反应是写BFS枚举保底，然后把它当成对拍器。Floyd适合时间紧又不想动脑的时候用来“垫分”，但不要把它当成学习目标——会用Floyd不算懂这题，能把换根DP写出来才算真懂。

3. 正解的推导：树上的带权重心与二次扫描换根

3.1 为什么这是一道换根DP题

暴力写法把每个点都当成医院算一遍，重复计算了大量信息。换根DP的核心思想是：只完整计算一个点当医院的答案，其余点由它的邻居答案“递推”出来。

想象医院从父节点u移动到它的孩子v。这棵树的边u-v被“跨过”一次，而这棵树的节点可以被分成两块：

• v这棵子树里的所有居民，到医院的路径都少走了一条边，总代价减少sz[v]；
• v子树之外的所有居民，到医院的路径都多走了一条边，总代价增加tot - sz[v]。

这里的sz[v]是v子树内的居民总数，tot是整棵树的居民总数。于是就有了全题最核心的转移公式：

dp[v] = dp[u] - sz[v] + (tot - sz[v]) = dp[u] + tot - 2 × sz[v]

理解这个公式的等价说法是：把每一条边看作“管道”，医院位置移动时，经过这条边的流量方向发生反转，代价差就是两边人数的差。

3.2 第一次遍历：以1为根统计子树人口与内部代价

换根DP需要两次DFS。第一次DFS以任意节点为根（代码里取1号点），从它向下递归，求出两个东西：

• sz[u]：以u为根的子树内居民总数；
• dp[u]：仅考虑u子树内的居民，让这些居民走到u的总代价。

第一次DFS的转移是：

sz[u] = w[u]; dp[u] = 0; if (lc) { dfs1(lc); sz[u] += sz[lc]; dp[u] += dp[lc] + sz[lc]; // 孩子子树内部先走到孩子，再统一走一条边到u }

dp[lc] + sz[lc]的意思是：孩子子树里每个居民要先汇到孩子节点，这部分代价是dp[lc]；然后再从孩子节点走一条边到u，因为lc子树里有sz[lc]个居民，所以额外加sz[lc]。注意这里边的代价是1，所以乘以的是1，不是距离层级。如果边权是c，就得乘c，这个后面扩展题会用到。

第一次DFS跑完，dp[1]就是“医院设在1号点时，全体居民到1号点的总距离”。这是唯一的“全量计算”，后面所有点的答案都由它推出。

3.3 第二次扫描：从父答案推出子答案

第二次DFS从根开始，利用转移公式把父节点的答案推给孩子节点。

void dfs2(int u) { ans = min(ans, dp[u]); if (lc) { dp[lc] = dp[u] + tot - 2 * sz[lc]; dfs2(lc); } if (rc) { dp[rc] = dp[u] + tot - 2 * sz[rc]; dfs2(rc); } }

注意公式里的tot是全局居民总数，就是sz[1]。每次往孩子走，用父节点的dp和两个孩子各自的子树大小，算出孩子节点的dp，然后继续递归。整个过程只做一次全树遍历，所以复杂度是O(n)。

这里的tot - 2*sz[child]可以看作“换根带来的增量”。如果孩子子树的人口超过总人口的一半，增量是负数，说明往这个孩子方向走能让总代价变小；如果不超过一半，增量非负，说明这个孩子方向不是更优的方向。这就是带权重心的判断条件的雏形。

3.4 直观理解与验证

拿一个简单链状树验证这个公式，比如：三个节点排成一条链，1号节点300人，2号节点一人没有，3号节点100人，左右孩子关系为1的左孩子=2，2的左孩子=3。

第一次DFS后：

• sz[3] = 100，dp[3] = 0；
• sz[2] = 100，dp[2] = dp[3] + sz[3] = 100（3号点100人走到2号，每人1条边，共100）；
• sz[1] = 400，dp[1] = dp[2] + sz[2] = 100 + 100 = 200（2号和3号的居民合计100人，再加1号点300人自己，实际总代价是200，因为医院在1号，3号100人走2条边，达200）。

然后换根到2号：

• dp[2] = dp[1] + tot - 2*sz[2] = 200 + 400 - 200 = 400？

不对，重新算一遍。dp[1]=200是指医院设在1号点，全体居民到1号的总距离：1号300人×0 + 3号100人×2 = 200。对。

换根到2号，公式dp[2] = dp[1] + tot - 2*sz[2] = 200 + 400 - 2×100 = 400。但实际上医院设在2号，总距离是300×1 + 100×1 = 400。公式算出来是对的，和我手算一致。这里2的sz是100（2号自己的0人+3号100人），所以总人口400减去200得增量200，正好等于1号方向300人多走一条边300，减去3号方向100人少走一条边100，净增200。逻辑对上了。

再用该公式往3号推：dp[3] = dp[2] + tot - 2*sz[3] = 400 + 400 - 200 = 600，手算：300人走2条边600，医院在3号确实总代价600。所以该链最优解是医院设在2号，总代价400。这也符合直觉——2号居中，两边人口差不多。

4. 手把手实现：完整C++代码与四个容易翻车的细节

4.1 建树与读入：孩子为0，数组要清零

P1364的节点编号从1开始，0表示空孩子。写代码时优先用全局数组，因为全局数组自动清零，不用手动memset。如果图省事把数组定义在main里，一定记得memset(lc, 0, sizeof(lc))，否则上一次测试数据可能污染这次结果。我在现场赛就吃过这个亏——本地数组第二次循环时会带着上一组的残留值。

另一个容易漏掉的点是：邻接表存双向边。如果只存单向的孩子关系，Floyd和BFS都会出错。初步判断自己是不是理解对了，就看代码里有没有为每条边push两次。

4.2 BFS暴力版的vis重置与距离累加

BFS暴力版最经典的bug是：多次BFS共用同一个dist数组，第二次BFS开始时没把dist全部重置成-1。如果只把起点s的距离置0，上一次BFS留下的旧距离会被新BFS读到，导致累加结果莫名其妙变很小。

建议每次BFS都新建一个vector<int> dist(N, -1)，成本不高，但能杜绝这类问题。另外，在BFS的累加逻辑里，res += w[v] * dist[v]这句一定要在入队时做，不要在出队时做。出队时做虽然也能算对，但会多算一次起点本身（起点dist为0不影响），逻辑上更容易绕晕，还是把维护工作放在入队时最清晰。

4.3 树形DP用int还是long long

这题n≤100，每个节点的居民数我记得上限是100，所以tot ≤ 10000，dp最大大概在 10^6级别，int完全没问题。但做题养成的习惯是，树形DP涉及累加时直接开long long。原因很简单：题目改一个数据范围，int就可能溢出，而long long几乎不会。尤其当你从P1364扩展到n=10⁵的变体题时，这个习惯能帮你少挂一次测试点。

4.4 完整可交代码（换根DP）

下面这份代码是正解，C++17提交即可。

#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 105; int n; int w[N], lc[N], rc[N]; ll sz[N], dp[N]; ll ans; void dfs1(int u) { sz[u] = w[u]; if (lc[u]) { dfs1(lc[u]); sz[u] += sz[lc[u]]; dp[u] += dp[lc[u]] + sz[lc[u]]; } if (rc[u]) { dfs1(rc[u]); sz[u] += sz[rc[u]]; dp[u] += dp[rc[u]] + sz[rc[u]]; } } void dfs2(int u) { ans = min(ans, dp[u]); if (lc[u]) { dp[lc[u]] = dp[u] + sz[1] - 2 * sz[lc[u]]; dfs2(lc[u]); } if (rc[u]) { dp[rc[u]] = dp[u] + sz[1] - 2 * sz[rc[u]]; dfs2(rc[u]); } } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> w[i] >> lc[i] >> rc[i]; } dfs1(1); ans = dp[1]; dfs2(1); cout << ans << endl; return 0; }

代码的骨架就是两次DFS。第一次从1号点往下走，把整棵树捋一遍，得到每个子树的sz和dp；第二次再往下走，一边走一边用公式推孩子的答案，并记录全局最小值。这里有个值得注意的点：dfs2里的sz[1]就是总人口tot，因为1号点是第一次DFS的根，它的sz等于全员。直接用sz[1]写公式，比额外开一个tot变量更少出错。

4.5 一个关于“二叉树”的提醒

我在文章开头提过，这题最大的坑是把“二叉树”理解成“只能往子树走”。但正解代码里，第二次DFS恰恰是从上往下推的，看起来好像也是“只走下边”——为什么不漏？关键在dp[u]的定义：它不是“以u为根的子树从u向下所有居民的距离”，而是整棵树所有居民到u的总距离。第一次DFS算的是局部，第二次DFS用公式把父节点的全局值转化成了子节点的全局值。所以即使代码只向下走，也没有丢失父方向的信息，因为父方向的代价已经藏在dp[u]里了。

如果非要检验自己是否理解，可以试试把代码里的dfs2改成从任意叶子往上推，或者把根从1换成别的节点跑一遍，看看最终答案是否一样。理论上换根的结果是等价的，这是树形DP“根无关性”的表现。

5. 从P1364到一类题：带权重心还能怎么考

5.1 题型识别：什么时候用换根DP

刷题多了之后，你会发现以下句型都是换根DP的“通缉令”：

• “在树上选一个点，使所有点到该点的距离之和最小”；
• “选一个位置建仓库/医院/学校，使运输总费用最小”；
• “各点有权值，边有权值，求Σ(点权×点到选择点的距离)最小”；
• “一条链上开会，所有人走路总时间最短”。

一旦出现在树上的这类题，第一反应就应该是带权重心。数据范围如果n≤2000，暴力枚举O(n²)没问题；n≤10⁵甚至更大，就必须写二次扫描换根。

5.2 变式题怎么扩展公式

原题边权都等于1，所以公式里的系数是1。如果边权不同，比如一条从u到v的边有花费cost，转移公式变成：

dp[v] = dp[u] + (tot - 2 × sz[v]) × cost

推导完全一样，只是跨过这条边时，子树内每个人减少的是cost，子树外每个人增加的也是cost。如果点权变成边权（每条边本身的通行费用由经过人数决定），又可以把边权拆成“边上所有人加起来”的形式，再套公式。这些变式在竞赛里都有对应题目，理解了P1364原型，基本上可以直接套模板改两行。

5.3 我的做题习惯与实操建议

最后分享几个我的实操习惯，希望能少走点弯路。

第一，先写暴力，再写正解，对拍验证。对P1364这种小数据题，先交一个Floyd或者BFS暴力版本，再用正解和它对拍几百组随机数据。随机数据用链、满二叉树、随机二叉树三种形态各生成一些，覆盖形态差异。暴力版和正解结果一致，才说明换根DP写对了。

第二，递归深度问题提前预判。P1364的n=100，递归深度最多100，无所谓。但如果复制这个模板去做n=10⁵的题，链状树会让递归深度爆栈。到时候要么改成显式栈迭代，要么在比赛环境下用#pragma comment(linker, "/STACK:102400000,102400000")（Windows下）或者加大栈空间（Linux下）。更稳妥的做法是练习时就用迭代版DFS，或者用std::vector模拟栈来转移树形DP。

第三，把这类题归类成“换根DP模板”单独记笔记。树上最长路径、树的直径、带权重心、以及“树上选两个点使距离最大/最小”这类题，解法套路都很接近：第一次DFS求子树的某个量，第二次DFS用父节点的答案推导子节点。模板一旦建立，再遇到类似的题就非常省力。

回到P1364本身，这题的真正价值不在于让你AC一道二叉树题，而在于让你建立“从暴力到优化”的完整思维路径。先会暴力BFS，再会Floyd，最后理解换根公式，一套流程走下来，带权重心这个知识点才算真正扎进脑子里。做题时不妨多问自己一句：如果n开大十倍，我的代码还能过吗？这个问题问多了，很多看似“碰运气”的AC，就会变成真正有把握的AC。