最近在洛谷刷树论题单发现“树的重心”这个知识点非常值得花时间认真过一遍。P1395和P2986正好组成一对很好的模板一个是无权重心的经典题一个是带权重的实战题配合P1670做补充练习基本能把这个模型吃得比较透。树的重心简单说就是在树上找一个点把这个点删掉之后剩下的若干棵子树里最大的那棵子树大小最小。这个点就是整棵树的重心。别看定义短它背后的性质和应用场景相当多比如“所有点到某个点的距离之和最小”这类问题本质上就是在找带权重心的位置。这篇文章我把自己做这三道题时用到的方法、推导过程、踩过的坑全部整理出来给准备刷树形DP和DFS模板的同学一个可以直接照抄的参考。1. 树的重心到底是什么先建立直观1.1 从“删掉一个点”说起很多教材喜欢把重心的定义说成“删除该点后最大连通块大小最小”。我当初学的时候这句话读了三遍才反应过来它是什么意思。一棵树有n个节点随便选一个节点u删除原来的树就会分裂成若干个连通块。如果u不是叶子那么连通块的数目等于u的度数连通块的大小则各不相同。其中最大的那个连通块有多大不同的点删出来的结果不一样。重心就是让这个“最大连通块”尽可能小的点。举个例子一条链上有5个点删掉中间那个点后左右各剩2个点最大连通块是2删掉端点的话剩下的连通块大小是4。所以链的重心是中间点。这个例子虽然简单但能很清楚地看出重心的一个直觉含义它是树的“质量中心”把树撑起来最平衡的位置。1.2 两条必须记住的性质围绕重心有两条非常常用的性质做模板题时直接决定了解法选型。第一条如果一个点是重心那么删掉它之后每一棵子树的大小都不超过n/2。反过来满足这个条件的点一定是重心。这条性质通常用来做“只求重心编号”的题目写法就是一个DFS维护子树大小最后检查每个点所有分支的最大值是否满足条件。第二条所有点到某个点的距离之和在重心处取到最小值。注意这里的“距离之和”是每条边上路径长度加总也就是常说的树上距离和。这一条是P1395和P2986的真正考点。要求最小距离和只靠找重心编号还不够还需要用换根DP算出具体的最小值。1.3 无权与带权同一个内核两套写法无权重心的场景是“每个节点的权重相同”求的是“n个点走到哪里总距离最短”。带权重心则给每个点一个权值比如P2986里每个牧场有若干头牛那么问题就变成了“总共多少头牛走的总路程最短”。此时每个节点的“大小”不再等于1而是等于该节点的权值子树大小也要改成子树权值之和。形式上两者需要维护的数组不一样无权时维护子树的节点个数带权时维护子树的权值总和。但是换根DP的转移公式长得非常像差一个系数而已。理解了无权版本的推导带权版本几乎可以直接套。2. 用DFS求重心两种写法的选择2.1 只求编号一次DFS维护最大子树先说只求重心编号的情况。以任意点为根做一次DFS在回溯过程中计算每个节点的子树大小。对于节点u删掉u之后产生的连通块有两类一类是原来u往下的子树这类连通块的大小就是各个子节点的子树大小另一类是u上方那一整块大小是n减去u的子树大小。取这两类中的最大值就是“删掉u后最大连通块大小”。代码模板如下#include bits/stdc.h using namespace std; const int N 100005; int n, sz[N], maxPart[N]; vectorint g[N]; void dfs(int u, int fa) { sz[u] 1; maxPart[u] 0; for (int v : g[u]) { if (v fa) continue; dfs(v, u); sz[u] sz[v]; maxPart[u] max(maxPart[u], sz[v]); } maxPart[u] max(maxPart[u], n - sz[u]); } int main() { cin n; for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs(1, 0); int ans 1; for (int i 1; i n; i) if (maxPart[i] maxPart[ans]) ans i; cout ans endl; return 0; }注意这里每一棵子树的大小都通过回溯累加而n - sz[u]处理的是“父亲方向”的那一块。这是树形DFS里非常基础也非常重要的思想把树当作有根树来遍历但用n - sz[u]把“上面的部分”也转化成子树大小来比较。2.2 求最小距离和引入换根DP如果题目不仅要求重心的编号还要求输出最小距离和这就不能只做一次DFS了。因为“距离和”是相对于某个根来说的需要知道所有点到根的距离总和。经典做法分两步第一步任选一个节点作为初始根比如1号点DFS一遍求出每个节点的深度。以1为根时所有点到1的距离和就是所有节点深度之和。第二步考虑把根从u移到孩子v距离和会怎么变化。原来在v这棵子树里的节点它们到根的距离都会减1不在v这棵子树里的节点到根的距离都会加1。设v的子树大小为sz[v]那么距离和的变化量就是新距离和 旧距离和 (n - sz[v]) - sz[v] 旧距离和 n - 2 * sz[v]这个公式非常关键。它说明只要知道父节点的距离和就能O(1)推出子节点的距离和。第二次DFS时用这个公式数组记下每个点为根时的距离和取最小值即可。2.3 复杂度分析两次DFS都是每个节点只访问常数次总复杂度O(n)。存储邻接表用vector空间O(n)。这个复杂度几乎是树形DP的最优形态所以这类题的数据范围可以给到10的5次方甚至更大递归写法仍然安全。3. P1395实战无权重心的模板题3.1 先把题意拆清楚P1395的要求是先找到树的重心然后输出这个重心以及所有节点到它的距离之和。如果存在多个重心输出编号较小的那个。这里的“存在多个重心”很好理解最典型的就是偶数节点的链中间两个点都是重心。所以在维护答案时比较条件要写成“更小才更新”不能加等号否则后遍历到的同值节点会把编号更大的节点覆盖进去。3.2 转移公式怎么落到代码里第一次DFS时我需要维护两个数组sz[u]表示子树大小dep[u]表示从初始根到u的深度。以1为初始根那么根1的距离和就是所有dep相加。这个和记为sum。第二次DFS按顺序访问每个节点v当从父节点u走到v时dp[v] dp[u] n - 2 * sz[v]这个dp数组的含义是“以v为根时所有节点到v的距离总和”。因为第一次DFS已经确保父节点的dp值是对的那么用这个公式递推下去所有节点的dp值都会是对的。同时比较dp值维护最小值和对应节点编号。3.3 完整AC代码#include bits/stdc.h using namespace std; typedef long long ll; const int N 50005; int n; ll sz[N], dep[N], dp[N]; vectorint g[N]; void dfs1(int u, int fa) { sz[u] 1; for (int v : g[u]) { if (v fa) continue; dep[v] dep[u] 1; dfs1(v, u); sz[u] sz[v]; } } void dfs2(int u, int fa) { for (int v : g[u]) { if (v fa) continue; dp[v] dp[u] n - 2 * sz[v]; dfs2(v, u); } } int main() { cin n; for (int i 1; i n; i) { int u, v; cin u v; g[u].push_back(v); g[v].push_back(u); } dfs1(1, 0); for (int i 1; i n; i) dp[1] dep[i]; dfs2(1, 0); int idx 1; for (int i 2; i n; i) if (dp[i] dp[idx]) idx i; cout idx dp[idx] endl; return 0; }这里dp数组我用了long long因为最坏情况下树是链n等于5万时所有点到端点的距离和可能接近12.5亿int不够稳妥。判题环境如果开了64位还好但自己写的时候直接开long long是最省心的。3.4 易错点第一递归入口传的父节点要设置成0或-1。因为树的节点编号从1开始父节点用0不会和任何实际节点冲突判断v fa时能准确跳过反向边。第二计算初始距离和时不能直接dp[1] 0因为1号点作为根时所有节点的深度要累加进去。这里容易漏漏了之后所有dp值都会比正确答案小而且不好排查。第三多个重心时取编号较小者所以最后的查询循环中用的是而不是。这个细节考场上很容易被忽略但如果题目特意加了“编号较小的重心”不处理就是白丢分。4. P2986实战带权重心的完整推导4.1 题面怎么转化为换根DPP2986对应的是一道USACO题大意是平面上有n个牧场每个牧场有若干头牛牧场之间有道路连接构成一棵树。要在某个牧场举办集会所有牛都要从自己的牧场走到集会地点问所有牛总路程的最小值是多少。这道题和P1395的最大区别在于两点第一每个牧场有权值c[i]表示牛的数量第二道路带长度w不能简单看作每条边距离为1。于是“总路程”等于每头牛走的距离之和也就是Σ(每个节点的权值 × 该节点到集会点的路径长度)。4.2 换根公式推导依然先选1号牧场作为初始根。第一次DFS时维护sz[u]为子树内所有牛的权值总和维护dist[u]为节点u到1号点的路径长度。初始集会点设在1号点时总路程是dp[1] Σ (c[i] * dist[i])这个值把所有牧场到1号点的距离乘以牛的数量再加总直接作为初始答案。现在假设集会点从u移动到它的孩子v边权为w。v子树那头有sz[v]头牛这些牛每人少走w路程所以总路程减少sz[v] * w。其余牧场一共有tot - sz[v]头牛这些牛每人多走w路程所以总路程增加(tot - sz[v]) * w。净变化量dp[v] dp[u] - sz[v] * w (tot - sz[v]) * w dp[u] (tot - 2 * sz[v]) * w这就是带权版本的换根转移公式。对比无权版本公式唯一区别是把节点数n换成了总权值tot并在变化量里乘上了边权w。所以只要理解无权重心的推导带权版本完全不需要额外记忆。4.3 完整AC代码#include bits/stdc.h using namespace std; typedef long long ll; const int N 100005; struct Edge { int v, w; }; int n; ll c[N], sz[N], dist[N], dp[N], tot; vectorEdge g[N]; void dfs1(int u, int fa) { sz[u] c[u]; for (auto e : g[u]) { int v e.v, w e.w; if (v fa) continue; dist[v] dist[u] w; dfs1(v, u); sz[u] sz[v]; } } void dfs2(int u, int fa) { for (auto e : g[u]) { int v e.v, w e.w; if (v fa) continue; dp[v] dp[u] (tot - 2 * sz[v]) * w; dfs2(v, u); } } int main() { cin n; for (int i 1; i n; i) { cin c[i]; tot c[i]; } 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}); } dfs1(1, 0); for (int i 1; i n; i) dp[1] c[i] * dist[i]; dfs2(1, 0); ll ans dp[1]; for (int i 2; i n; i) ans min(ans, dp[i]); cout ans endl; return 0; }这道题不需要输出聚集点的编号只需要最小总路程所以最后取最小值即可。4.4 一个我踩过的坑我第一次写P2986时把sz[u]的初始化写成了sz[u] 1完全忘记节点有权值。结果样例过得很顺利一交上去就是WA当时整个人都是懵的。问题的根源在于带权重的场景里子树大小的含义已经从“节点数量”变成了“牛的数量”这两个值只有在所有权值都为1时才等价。所以写带权换根DP时第一步就要明确“我维护的sz到底是什么”一定是用sz[u] c[u]作为起点再往下累加子节点。另一个坑是总牛数tot必须读入所有权值后累加得到不能在DFS过程中动态加。换根公式里用到的是全局不变的总量不是某个子树的值这个顺序不能颠倒。5. 三题串起来从模板到变式的刷题路线5.1 建议的刷题顺序我自己的顺序是先写P1395把无权重心的DFS和换根DP跑通再写P2986把代码里的节点数改成权值总和、把边权1改成长度w最后再碰P1670这类综合性更强的题目。P1670并不像前两题那样直白地告诉你“求重心”它更看重对树的各种结构的理解。我的看法是别急着做它先把P1395和P2986的公式自己独立推导两遍等能熟练写出换根DP了再去做P1670你会有完全不一样的感觉。5.2 同一套公式能解决哪些变式树的重心这一套东西变形很多但核心公式就那两个无权时dp[v] dp[u] n - 2 * sz[v]带权时dp[v] dp[u] (tot - 2 * sz[v]) * w这两个公式可以覆盖一类问题在一棵树上选一个点使得所有点到它的加权距离和最小。不管题目是求“开会最省路程”还是求“快递站建哪里最方便”还是求“服务器部署在哪里网络总延迟最低”本质都一样。如果题目还要求“若有多个点满足输出编号最小”改动也极其简单在最终比较时用严格小于号即可。这个思路可以迁移到很多“取最优解”的树形DP题里。5.3 题目信息对比速查表题目目标节点规模边有无权值是否带点权核心解法P1395输出重心编号和最小距离和约5e4无权边权1否换根DPP2986输出最小总路程约1e5有边权是带权换根DPP1670综合性练习需先掌握前两题看具体数据范围需要观察需要观察树论综合应用做题时先判断两点每个点的初始“大小”是1还是给定的权值每条边移动一步的代价是1还是w判断完这两个问题公式怎么写就有了方向。6. 常见问题与排查心得6.1 递归爆栈怎么办树形DFS最怕遇到链式数据n一达到10的5次方递归深度就可能让程序栈溢出。很多OJ会因此返回RE而不是WA第一次遇到时很难想到是栈空间问题。稳妥的办法是先把模板写成递归形式本地小数据验证正确性再交给在线评测。如果题目数据范围特别大或者你是用一些默认栈空间很小的环境做练习可以改成非递归的手工栈写法。不过以洛谷的常规题目来说10的5次方级别的递归栈通常可以过不用过度担心。实际比赛中如果实在不放心你可以在代码开头使用操作系统层面的栈扩展指令但这个方法换平台会失效我的建议是平时练题用递归心里清楚有栈上限这件事就好。6.2 双向边漏判断导致的死循环树的DFS最经典的错误就是忘了判断父节点导致在父子节点之间来回递归。具体表现是程序直接栈溢出崩溃或者TLE。写邻接表时记得双向push_back遍历时用if (v fa) continue;跳过父节点。如果节点编号从1开始初始调用就写成dfs(1, 0)因为0号节点不存在不会被误判跳过合法节点。6.3 换根公式的符号怎么验证考场上一紧张公式记反的情况太常见了。我的验证方法是拿一条链手工推一遍。比如一条3个点的链1-2-3。以1为根时距离和是0123。把根从1换到2节点2的子树里只有节点3和节点2本身sz[2]2那么新距离和应该是33-2*22实际上所有点到2的距离和确实是0112。这个推导成立说明公式没记反。如果算出来大于3那就是加减号或者倍数出了问题。这个方法比背公式更可靠。因为刷题多了你会发现公式背得再熟不如能快速推导来得踏实。6.4 从背代码到推公式最后说一点个人感受。树的重心这类模板题网上代码一搜一大把照抄十分钟就能AC。但真到比赛或者面试白板编程时能写出来的都是那些把“为什么是n减2倍sz”想清楚了的人。我的建议是做完整理之后把三行核心公式遮住自己从零推导一遍。推导的起点就是“集会点从当前点移到孩子节点谁多走路谁少走路”。把这个过程想明白带权版换根DP、甚至更多的变式你都能顺手解决。这个推导习惯比多刷十道模板题给我的帮助更大。