前两天在洛谷刷题刚好把 P1670、P1395、P2986 这三道跟“树的重心”有关的题放在一起写了。三题看着各不相同一个要输出重心一个要算会议距离一个要算奶牛集会的最小路程实际上核心模板就一个DFS 一遍算出子树大小然后根据“删掉某个点之后最大连通块最小”去选答案。这篇文章不打算只贴板子我想把定义、性质、带权重心和换根 DP 之间的逻辑关系讲清楚同时把我自己写模板时踩过的坑放进来。适合刚学树形 DP 的同学也适合准备 ACM/蓝桥杯、洛谷刷题时想直接抄一套可靠模板的人。1. 树的重心一句定义背后藏着三个性质1.1 重心到底是什么树的重心的定义非常简单在一棵有 n 个结点的树中如果删除结点 u树会分裂成若干个连通块这些连通块中结点数最大的那个记为 f(u)。我们要找的就是让 f(u) 最小的那个 u。换句话说重心是“删除之后剩下的最大块尽量小”的那个点。举个例子一条长度为 5 的链重心出现在中间那个点。删掉中间点左右两边各剩两个点最大块是 2这是整条链上的最小值。如果是星形树重心就是中心点删掉它之后每个叶子都是独立块最大块是 1。这两个例子能帮你快速建立直觉重心往往在树的结构“平衡点”附近它让整棵树在删除操作后不至于留下一个特别大的残余块。1.2 三个必须记住的性质第一个性质以重心为根所有子树的大小都不超过整棵树大小的一半。这是重心的等价定义很多题目判断“某个点是不是重心”就用这个条件对每个邻接点 v如果 sz[v] * 2 n那么 u 就不是重心重心一定在 v 方向。这个条件也能直接用来找重心后面我讲的带权重心移动法就是从这里来的。第二个性质一棵树最多有两个重心而且如果有两个它们一定相邻。为什么会相邻因为两个重心之间的那条边会把树分成大小完全相等的两半这种结构只在特殊情况下出现。做洛谷题目时经常遇到要求输出编号最小的那个或者把两个都输出这就要在模板里对 f(u) 相同的情况下做编号比较。第三个性质重心到所有结点的距离和是最小的。这里的“距离和”是指每条边权视为 1 时的路径长度总和。这个性质最实用P1395 开会、P2986 奶牛集会这类“所有人都走到一个点求总路程最小”的问题本质上就是在找带权重心而无权情况下重心就是距离和最小的点。1.3 哪些题在背后等你树的重心不是一个孤立考点它是点分治、树哈希、动态树问题里的常见前置步骤。点分治每层都要找当前连通块的重心复杂度才能保证在 O(n log n)树哈希如果不先确定重心一棵无根树会因为根选不同而算出不同的哈希值经常导致判重失败。所以我会建议你把这一套模板当成基础工具背熟而不是只为了过三道题。2. 无权重的重心DFS 一次后序就够了2.1 核心递推式是怎么来的先选定 1 号点为根做一遍 DFS求出以每个结点为根的子树大小 sz[u]。递归的时候u 的所有子结点 v 的子树大小我们知道u 的父方向还有一个“隐藏的连通块”它的大小是 n - sz[u]。删除 u 之后最大连通块的大小就是f[u] max( max(sz[v]) for v in children, n - sz[u] )求重心时我们只需要遍历所有结点找出 f[u] 最小的那个。因为每个结点的 sz 只依赖子结点所以一次后序遍历就能同时完成子树大小计算和 f[u] 更新不需要真的“删除”任何东西。这里最容易犯错的地方就是父方向那一块。很多初学者跑完子树大小之后只比较子结点 sz[v]忘了算 n - sz[u]导致根附近的点几乎不可能被选成重心。实际上对于根节点n - sz[root] 是 0所以根不会吃亏但对非根结点父方向往往是一个很大的连通块漏掉它会让结果完全错误。2.2 一次 DFS 写完模板下面是我常用的无权重重心模板。因为 DFS 是后序的子树的 sz 计算完成后马上更新 f[u]最后再维护全局最小值。#include bits/stdc.h using namespace std; const int N 200010; vectorint g[N]; int n; int sz[N]; int best; // 当前最小的最大连通块大小 int centroid; // 当前找到的重心编号 void dfs(int u, int fa) { sz[u] 1; int max_part 0; for (int v : g[u]) { if (v fa) continue; dfs(v, u); sz[u] sz[v]; max_part max(max_part, sz[v]); } // 父方向那一块 max_part max(max_part, n - sz[u]); if (max_part best) { best max_part; centroid u; } } int main() { scanf(%d, n); for (int i 1; i n; i) { int u, v; scanf(%d%d, u, v); g[u].push_back(v); g[v].push_back(u); } best n 1; dfs(1, 0); printf(%d\n, centroid); return 0; }这个模板的时间复杂度是 O(n)空间复杂度 O(n)。为什么能一次 DFS 解决因为 max_part 是后序更新遍历到 u 时所有子树的 sz[v] 已经确定而 n - sz[u] 只需要在最后用全局 n 减一下就行。不需要第二次 DFS。2.3 多重心怎么输出如果题目要求输出两个重心就不能只用更新要改成当 max_part best 时清空候选列表当 max_part best 时把 u 加进候选列表。因为重心最多两个列表长度最多是 2。输出时按编号排序一下就好。if (max_part best) { best max_part; ans.clear(); ans.push_back(u); } else if (max_part best) { ans.push_back(u); }我遇到过一些题目虽然没有明确说要多重心但测试数据里刚好有偶数个结点的链这种树恰好有两个相邻重心。如果你只输出其中任意一个部分判题点可能因为“答案不唯一”而不给 AC。稳妥起见模板最好从一开始就支持多重心反正多写两行也不影响性能。3. 带权重心从“数结点”到“数和权值”的思路升级3.1 带权重心是什么在很多应用场景里每个点并不等价。P1395 中每个结点可能住着不同数量的人P2986 中每个结点有不同数量的奶牛所以我们要找的点要满足所有人的移动距离之和最小或者所有奶牛走路程之和最小。这种问题叫带权重心或者加权中位数问题。定义上带权重心的目标函数是sum( w[i] * dist(i, x) )其中 w[i] 是点权dist(i, x) 是 i 到 x 的距离。注意这个距离在 P2986 里还带边权因为每条牧场道路长度不同。无权重重心可以看作是所有 w[i] 1 的特例。所以一个很自然的想法是把上一节的 sz[u] 从“子树结点个数”改成“子树的权值和”依然用同样的逻辑找“删掉之后权重最大块最小”的点。但带权问题的目标函数是距离和最小这个目标并不完全等于“最大权重块最小”所以通常我会改用换根 DP 来直接求每个点的距离和而不是只找那个点。3.2 重心移动法一种省代码的找法如果你只想找带权重心不输出最小距离可以用“重心移动法”。过程是这样的随便选一个根求出每棵子树的权值和 total。从根出发检查当前的候选点 u如果存在一个子结点 v使得 sz[v] * 2 total说明超过一半的权重在 v 这个方向重心一定在 v 的子树里于是把 u 移动到 v继续检查如果父方向的权重 n - sz[u] 满足条件则向父方向移动。由于只有一个方向能超过一半最终会停在带权重心上。这个算法的正确性来自前面说的性质以重心为根所有子树权重都不超过总权重的一半。每次向权重超过一半的方向移动都会严格减少总距离所以不会陷入循环。代码上可以用循环加邻接表实现但需要维护父方向的信息比换根 DP 更容易写错。我一般只在“只要求重心编号、不要求距离和”的题里用。3.3 换根 DP一次 DFS 算出所有点的距离和换根 DP 才是带权重心类题目的标准解法。思路是先随便选一个根比如 1求出所有点到 1 的距离和 dp[1]同时求出每个子树的权值和 sz[u]然后从 1 开始往子结点转移。转移公式非常优雅。假设当前从 u 换到相邻点 v边权为 lenv 这个方向的子树权值和为 sz[v]全部权重之和为 total。原来所有点都到 u 集合现在改到 v 集合v 子树里的那些点本来要走到 u现在只需要走到 v 了。每个点的路程减少了 len总共减少 sz[v] * len。除了 v 子树以外的点本来走到 u现在要多走一条边才能到 v。总共有 total - sz[v] 这么多权重所以总共增加 (total - sz[v]) * len。于是dp[v] dp[u] - sz[v] * len (total - sz[v]) * len dp[u] (total - 2 * sz[v]) * len这是带权重心题目里最重要的一个式子。它能一次算出每个结点的距离和最后遍历一遍求最小值顺便记录编号。下面是一个同时支持点权和边权的模板。P1395 只需要把 len 当成 1P2986 直接把输入的道路长度放进去。#include bits/stdc.h using namespace std; using ll long long; const int N 200010; struct Edge { int v; ll len; }; int n; ll w[N]; // 点权 vectorEdge g[N]; ll sz[N]; // 子树权值和 ll dp[N]; // 以每个点为集合点的总距离 ll total; void dfs1(int u, int fa) { sz[u] w[u]; for (auto e : g[u]) { if (e.v fa) continue; dfs1(e.v, u); sz[u] sz[e.v]; dp[1] sz[e.v] * e.len; // 所有点先算到根 1 的距离和 } } void dfs2(int u, int fa) { for (auto e : g[u]) { if (e.v fa) continue; dp[e.v] dp[u] (total - 2LL * sz[e.v]) * e.len; dfs2(e.v, u); } } int main() { scanf(%d, n); for (int i 1; i n; i) { scanf(%lld, w[i]); total w[i]; } for (int i 1; i n; i) { int u, v; ll len; scanf(%d%d%lld, u, v, len); g[u].push_back({v, len}); g[v].push_back({u, len}); } dfs1(1, 0); dfs2(1, 0); ll ans LLONG_MAX; int pos 1; for (int i 1; i n; i) { if (dp[i] ans || (dp[i] ans i pos)) { ans dp[i]; pos i; } } printf(%d %lld\n, pos, ans); return 0; }3.4 为什么带权重心和换根 DP 是同一套 sz有人会问上一节无权重模板里的 sz 是子树结点数这里却变成子树权值和这两套东西能放在一起用吗当然可以。因为 DFS 的递归骨架完全一样变的只有“累加什么”。无权重累加 1带权累加 w[v]。你把带权模板里的 w[i] 全部改成 1求出的就是无权重的距离和把目标从找最小距离和改成找最大块最小就退化成了普通重心。这也是为什么我把它们打包成同一个模板记考试时只改初始化逻辑就行。4. 三道题串讲模板怎么落到题目里4.1 P1670验证模板本身P1670 这种题本质就是让你把第二节的无权重模板原样写上去。我见过很多同学把重心定义背得很熟但提交时少考虑了父方向的连通块导致 WA 在几个隐蔽数据上。把模板的 max_part 维护逻辑写好这道题基本就过了。如果你用的是我上面的代码注意一点题目如果要求输出“重心编号 最大块大小”就把 best 也一起打印。如果要求两个重心就把候选列表改成动态数组。我建议每次写题之前先看清输出格式因为“输出重心”和“输出重心的最大块”是两个不同的字段调用模板时很容易漏。4.2 P1395点权 边权为 1 的特例P1395 的题意接近“会议选址”每个点有人口边权默认为 1让你求所有人走到某个结点的总距离最小。这其实就是带权重心模板中 len 1 的情况。在代码上只需要把读入改成读树边w[i] 读入点权len 固定为 1。转移公式变成dp[v] dp[u] total - 2 * sz[v]因为 len 1甚至不需要用 long long 存边权但 dp 和 sz 仍然要开 long long。这题的细节是答案可能有多个点通常题目要求输出编号最小的那个所以在比较 dp[i] 相等时要维护最小编号。我做这道题时踩过一个坑思路完全对但读入时把点权的顺序和边的顺序写反了。P1395 前面读 n后面跟着 n 个点权接下来是 n - 1 条边。有一版模板把点权循环写成了 n - 1 次导致整个树的 sz 全部错乱调试了很久才发现。遇到这种“带点权”的树题我建议先把点权读完整再读边中间最好加一个注释区分。4.3 P2986边权不为 1 的版本P2986 是 USACO 的 Great Cow Gathering本质和 P1395 一样但多了边权而且数据范围更大。每个结点有奶牛数量每条路有长度要求所有奶牛走到集会点的总路程最小。这就是第三节模板的标准应用场景。需要注意total 是全部奶牛数量不是 n。sz[u] 是子树内奶牛数量之和不是结点数。dp 可能出现很大值比如 n 达到几万每条路长度几百奶牛数量上千乘积会超过 int。所以一定要用 long long 存 dp 和 sz。我测过一组极端数据一条链边权全取最大值点权全取最大值最后答案会达到 10 的 15 次方这个量级。如果你用 int不仅可能溢出成负数还会在比较大小的时候选出错误的最小点。这是带权模板最容易忽视的问题大家在刷 P2986 时务必把ll写满。三道题放在一起对比就很清晰了题号点权边权目标模板部分P1670无无输出重心编号/最大块无权重重心 DFSP1395有固定为 1最小距离和输出编号带权重心换根 DPP2986有有长度最小路程和输出编号带权重心换根 DP5. 模板化之后的细节坑递归、栈、long long 与扩展5.1 递归爆栈问题树形 DFS 最怕的是递归层数太深。一棵链状的树如果 n 1e5递归深度就是 1e5。在部分判题环境里这种深度可能会导致栈溢出程序直接段错误或 RE。我惯用的解决办法有三个。第一如果题目允许在 main 开头写一句system(ulimit -s unlimited);但有些平台不支持而且不优雅。第二在 Windows 上调试时可以用#pragma comment(linker, /STACK:102400000,102400000)不过 Linux 判题机上无效。第三实在不行就改成迭代栈模拟递归虽然代码长一点但稳。日常刷题我一般先写递归只有遇到 RE 且确认是栈溢出时才改迭代版。洛谷多数题目的栈空间足够 n 1e5不用太焦虑。5.2 邻接表的选择我推荐直接用vectorint或者vectorEdge简单清晰调试方便。如果追求极限性能可以换成链式前向星很多 OI 选手习惯用它int head[N], to[N*2], nxt[N*2], cnt; void add(int u, int v) { to[cnt] v; nxt[cnt] head[u]; head[u] cnt; }链式前向星比 vector 少一点内存碎片在递归几百万次时会略快。但如果你的目标是快速 AC 而不是卡常vector 完全够用。P2986 的数据规模不大vector 实测没问题。5.3 编号从 1 开始还是从 0 开始洛谷模板题几乎都是从 1 开始编号所以 dfs(1, 0) 是最稳妥的写法。如果遇到从 0 开始编号的题把 dfs 入口改成 dfs(0, -1)同时把返回值判断从if (v fa)改成if (v fa)逻辑不变。注意父节点要传一个不存在的编号不要传 0 又恰好有结点编号 0那就永远递归不出去了。5.4 模板扩展点分治和前向应用重心模板写熟之后点分治的框架就是顺水推舟。每层找一个当前连通块的重心然后只处理经过重心的路径再递归到每个子连通块。没有重心保证点分治的递归深度可能在链状树上达到 O(n)退化成暴力。所以“找重心”这一步是点分治性能的下限值得单独写成函数void get_centroid(int u, int fa, int total_nodes) { // 和第二节一样只不过 total_nodes 是当前连通块大小 }如果以后做树哈希你也可以先把重心找出来再把整棵树转成以重心为根的有根树再算哈希值。这样同一棵树无论从哪里开始读入哈希结果都一样非常实用。最后说两句我的使用习惯我在洛谷刷题时习惯把无权重重心和带权重心的代码各存一份放到同一个代码模板库里。无权重那份用来应付纯模板题和点分治带权那份用换根 DP遇到 P1395、P2986 这类“所有人走到一个点”的题直接改点权的读入就行。有一个小技巧分享给大家如果你不确定题目要求的是“最大块最小”还是“距离和最小”可以先对样例手算一下。比如 P2986你随便找一个叶子结点算一次总路程再和中点算的值比较立刻能判断目标函数对不对。比对着题目描述反复抠字眼快得多。模板这种东西重要的不是背下来而是知道每一行为什么这么写。把n - sz[u]、total - 2 * sz[v]、best ans这三个变量的含义吃透树的重心这个大题类型就基本拿下了。