做算法题的人应该都有体会树形结构里但凡牵扯到“删一个点”、“找一个最优位置”、“算所有点到某点的距离和”最后十有八九会落到一个东西上——树的重心。洛谷的P1670、P1395、P2986这三道题恰好是一条非常完整的进阶链路从裸模板到带权重心从“找点”到“算距离和”把它们吃透树的重心这类题基本就稳了。这篇文章我把这三道题放在一起拆核心就讲清楚三件事树的重心怎么用DFS求、带权重心和普通重心的区别在哪、换根法到底在换什么。适合已经会建图、会写最基础DFS的读者也适合准备系统性刷树论、冲击省选模板题的选手。我会把原理、代码、易错点全部摊开讲代码以C为例逻辑用Java或者其他语言照搬也没问题。1. 先搞清楚树的重心到底在求什么树的重心定义很简洁在一棵有n个节点的树里删掉某个点后剩下的森林中最大的那个连通块节点数最小。这个“删掉后最大连通块最小”的点就是树的重心。换句人话重心就是那种“你把树从它这里劈开剩下的最大一块尽量小”的点。举个例子一条长度为5的链节点1-2-3-4-5。你删掉节点3剩下的两块分别是[1,2]和[4,5]大小都是2最大是2。你删掉节点2剩下的是[1]和[3,4,5]最大是3。所以重心是3。这条链上重心甚至可能是两个当节点总数为偶数时比如节点1-2-3-4删掉2得到max(1,2)2删掉3得到max(2,1)2所以2和3都是重心。这个定义背后的直觉很实用如果你要在树上选一个地方修仓库、办集会、建立服务中心要求“最远的客户尽量近”或者“所有客户总路程尽量短”重心往往就是那个最优解。比如P1395题面里那种“在某个节点开会所有人走的路程总和最小”的需求本质就是在找重心后算距离和。树的重心有几个非常重要的性质刷题时直接当结论用重心最多有两个如果有两个它们一定相邻。以重心为根时任意子树的大小都不超过总节点数的一半。树上所有点到重心的距离之和是所有节点中最小的一组值。如果树上有边权或者点权只要把“节点数”替换成“权值”以上性质依然成立这就引出带权重心的概念。这些性质不需要死背你理解一遍DFS怎么算就记住了。下面我直接从最暴力的思路开始推看看为什么最后会收敛到那几行模板代码。2. DFS求重心原理和模板一次讲透2.1 为什么暴力做法不可行最直接的做法是枚举每个节点把它删掉然后DFS统计剩下的每个连通块大小取最大值。这样做一次统计是O(n)枚举n个点总复杂度O(n²)。题目数据规模只要到2万甚至5万立刻超时。所以必须一次DFS把所有信息算出来。关键点在于当你删掉某个节点u时剩下的连通块其实可以分成两类——一类是u的每个子节点所在的子树另一类是“u的父节点那一侧”.如果我们已经知道了以u为根时每棵子树的大小这两个部分的大小就都能算出来。这里需要先把树转成有根树。任选一个节点当根比如1号节点然后DFS一遍用size[u]表示以u为根的子树一共有多少个节点。那么u的子节点v对应的子树大小就是size[v]。u的父节点那一侧的节点数就是 n - size[u]。删掉u之后最大的连通块就是max(所有子树的size[v], n - size[u])。对每个u算出这个值取最小就找到重心了。2.2 一次DFS要记录哪些东西代码里只需要一个数组size再加上递归过程里的临时变量maxPart。递归的“后序”位置也就是先递归孩子再处理当前节点就是在做这件事递归到u时初始maxPart n - size[u]不行因为这时候父节点一侧的节点数还不知道size[u]还没完全算出来。正确顺序是先递归处理所有子节点让size[v]都有了然后再累加出size[u]最后才能用n - size[u]。这也是为什么这个DFS不能写成先处理当前节点再递归的“前序”形式必须先钻进孩子再回来汇总。我早期写过一次前序size全是0找了半天bug。2.3 模板代码#include bits/stdc.h using namespace std; const int MAXN 50005; vectorint g[MAXN]; int sz[MAXN]; // worst[u] 表示删除 u 后剩余连通块中最大的大小 int worst[MAXN]; int n; void dfs(int u, int fa) { sz[u] 1; // 先把最大连通块初始化为父节点那一侧 // 但因为此时 sz[u] 还没算完所以这里先只考虑父侧 // 准确做法是到后序位置再算 n - sz[u]目前先收集子树的 int maxSon 0; for (int v : g[u]) { if (v fa) continue; dfs(v, u); sz[u] sz[v]; maxSon max(maxSon, sz[v]); } // 后序位置此时 sz[u] 已经是完整子树大小 int parentPart n - sz[u]; worst[u] max(maxSon, parentPart); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); 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 center 1; for (int i 2; i n; i) { if (worst[i] worst[center]) { center i; } } cout center \n; return 0; }这个模板是“找编号最小的重心”。如果题目要求输出所有重心就在遍历完worst数组后把所有worst[i] worst[center]的i都输出即可。注意这里worst数组实际上只用到了“最大连通块大小”这个数值不需要真的建出森林再数节点。核心就是那句max(maxSon, n - sz[u])。这句话就是树的重心模板题的灵魂。2.4 简单验证一下拿节点1-2-3-4这条链验证。以1为根dfs(2)时先递归得到sz[3]。节点3的子树里只有4所以sz[3]2sz[4]1。节点2的maxSonsz[3]2parentPartn - sz[2]4-31所以worst[2]max(2,1)2。节点3在最外层dfs(1)里递归3的子节点4已经处理过sz[3]2maxSon1parentPart4-22所以worst[3]max(1,2)2。节点1maxSonsz[2]3parentPart0worst[1]3。worst最小是2节点2和3都是重心这个结果和前面手动推导一致。3. 从“数点”到“加权”带权重心与换根法3.1 带权重心要解决什么普通重心的每个节点权重都是1。带权重心就是每个节点有一个权值比如P2986里每个农场有c[i]头牛或者P1395里每个节点有一个人。此时“删点后最大连通块最小”的定义要改成“权值和最大的一块最小”。但注意带权问题往往是另一个形态不是“删点后最大块最小”而是“所有节点到某个点的加权距离总和最小”。这两个目标在某些问题里等价于重心但题目直接给的是后者。所以带权重心的核心考点其实是“如何在树上高效计算所有点到某个候选点的加权距离和”以及“如何从一个候选点快速得到相邻候选点的距离和”这就引出了换根法。普通重心题只要一次DFS就能做带权重心如果还是每个候选点都DFS一遍又是O(n²)。所以必须用换根DP把复杂度压到O(n)。3.2 换根法的核心转移公式假设每条边有边权w每个节点有点权val[i]。先任选一个根比如1号节点做一遍DFS求出sumW[u]以u为根的子树的权值和。total整棵树的权值和。dp[1]所有节点到1号节点的加权距离和。具体计算dp[u]的方法对孩子v的子树来说v子树的所有节点到u的距离等于它们到v的距离加上一条边w(u,v)所以dp[u] sum_{v是u的孩子} ( dp[v] sumW[v] * w(u,v) )这里的dp[v]意思是“v子树所有节点到v的加权距离和”加上sumW[v] * w就是把这些节点再往u挪一步。得到dp[1]后怎么算dp[u]这里u是任意节点而u现在是根换根的关键在于从父节点f走到子节点u跨越了边w(f,u)。想象整棵树被这条边分成两部分u这半边以及f那半边。跨过这条边后u这半边的所有节点到新根u变近了每接近w(f,u)就少一段距离总减少量就是sumW[u] * w。而f那半边的所有节点到新根u变远了总增加量就是(total - sumW[u]) * w。所以转移公式dp[u] dp[f] - sumW[u] * w (total - sumW[u]) * w dp[f] (total - 2 * sumW[u]) * w这个公式是带权重心的灵魂。它和“以1为根时每个节点子树权值和sumW[u]”绑定不管新根在哪sumW[u]都是固定的因为“以u为根的子树”在最初以1为根时就已经定义好了。3.3 代码实现#include bits/stdc.h using namespace std; const int MAXN 100005; struct Edge { int to, w; }; int n; long long val[MAXN]; long long sumW[MAXN]; long long dp[MAXN]; long long total 0; vectorEdge g[MAXN]; // 第一遍DFS求 sumW 和 dp[1] void dfs1(int u, int fa) { sumW[u] val[u]; for (auto e : g[u]) { int v e.to; int w e.w; if (v fa) continue; dfs1(v, u); sumW[u] sumW[v]; dp[1] dp[v] sumW[v] * w; // 也可以这样写 // dp[u] dp[v] sumW[v] * w; } } // 第二遍DFS换根求所有 dp void dfs2(int u, int fa) { for (auto e : g[u]) { int v e.to; int w e.w; if (v fa) continue; dp[v] dp[u] (total - 2 * sumW[v]) * w; dfs2(v, u); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 1; i n; i) { cin val[i]; total val[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); dfs2(1, 0); long long ans dp[1]; for (int i 2; i n; i) { ans min(ans, dp[i]); } cout ans \n; return 0; }有个细节dfs1里递归结束回到u后dp[1]累加了dp[v] sumW[v] * w但dp[v]在dfs1里的意义其实是“v子树内部所有节点到v的距离和”。这个值在下一层dfs1已经算好了。我一开始把dp数组初始化为0然后在dfs1里写成dp[u] dp[v] sumW[v] * w这样dp[u]存的是“u子树内所有节点到u的距离和”。这样做完全没问题且更容易理解。上面的代码为了简洁直接把累加放进了dp[1]你需要确保dp[1]在所有子节点都dfs完后才赋值。两种写法等价推荐写成dp[u]版本void dfs1(int u, int fa) { sumW[u] val[u]; for (auto e : g[u]) { int v e.to; int w e.w; if (v fa) continue; dfs1(v, u); sumW[u] sumW[v]; dp[u] dp[v] sumW[v] * w; } }这样dp[1]在dfs1结束后自然就是“所有节点到1的距离和”。3.4 从普通重心到带权重心的直觉变化普通重心可以认为是所有节点权值都为1的特例。你甚至可以用带权重心的代码把所有点权设为1边权设为1求出的dp数组最小值对应节点就是普通重心。而P1395其实就相当于这个特例。但反过来不行带权重心不能直接用普通重心模板因为点权和边权会改变重心的位置。P2986就是一个典型每个农场有牛、每条路有距离要使所有牛走的总路程最小这个“中心”很可能不在树的几何中心上而会偏向牛较多的农场。这也是为什么刷题顺序推荐先P1670再P2986先理解“重心是结构上的中心”再理解“给每个点加不同权重后中心会发生偏移”。4. 洛谷三题实战P1670、P1395、P2986怎么逐步升级4.1 P1670先把裸模板练熟P1670是一道最基础的模板题一般题意要求输出树的重心编号。唯一的坑可能是多组数据或者要求输出所有重心中编号较小的那个。用第2节的代码直接套即可。这道题我最初做的时候犯过一个低级错误题目没给n的数据范围我开数组太小RE了一次。给树的题数组大小至少按MAXN n 5开vector直接不用定死也行更稳妥。代码就不重复贴了用2.3节的模板把所有worst算出来后找最小即可。注意输出格式如果有两个重心有的题会要求输出编号较小的。4.2 P1395找到重心再求距离和P1395这道题通常是给定一棵树求一个节点使得所有节点到它的距离之和最小如果答案不唯一输出编号较小的点。这个题本质是普通重心距离和。先通过一次DFS找出重心然后以重心为根再做一次DFS累加所有节点深度这就是所有节点到重心的距离和。为什么重心能保证距离和最小前面说过树的重心性质所有点到重心的距离和最小。你可以这样理解如果你从重心往任意一个相邻节点挪一步跨过边后原来那一侧的k个节点到新点变远1另一侧的n-k个节点变近1总距离变化为(n-k)-k n-2k。重心满足k不超过n/2所以n-2k≥0也就是不会变好。这个性质用代码来验证更直观。这里只需要普通DFS不需要换根法因为只需要一个根的重心。// 先找到重心再用重心做DFS求距离和 #include bits/stdc.h using namespace std; const int MAXN 50005; vectorint g[MAXN]; int sz[MAXN], worst[MAXN]; int n, center, ansDist; long long sumDist 0; void dfs1(int u, int fa) { sz[u] 1; int maxSon 0; for (int v : g[u]) { if (v fa) continue; dfs1(v, u); sz[u] sz[v]; maxSon max(maxSon, sz[v]); } worst[u] max(maxSon, n - sz[u]); } void dfs2(int u, int fa, int dep) { sumDist dep; for (int v : g[u]) { if (v fa) continue; dfs2(v, u, dep 1); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); 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); center 1; for (int i 2; i n; i) { if (worst[i] worst[center]) center i; } // 如果有多个重心选择编号较小的这里注意题目要求 for (int i 1; i n; i) { if (worst[i] worst[center] i center) center i; } dfs2(center, 0, 0); cout center sumDist \n; return 0; }有时候P1395的题意还会要求“如果有多个重心输出编号最小的”上面已经处理了。这道题和P1670的区别就是多了个第二次DFS求深度和难度的提升不大但很关键它让你为P2986打好“距离和”的底子。4.3 P2986带权重心完整实现P2986的原题背景是奶牛集会给定n个农场每个农场的牛数量val[i]农场之间有n-1条路长度w。要求在所有农场中选一个作为集会地点让所有牛走的总路程最小输出最小总路程。这道题就是标准的带权重心用第3节的换根法。区别在于你要找的是dp数组中的最小值而不是重心本身。我在做这道题时踩过一个坑总路程可能很大要用long long。比如n10万每个点权值10万边权10万时最坏距离和是1e5 * 1e5 * 1e5 1e15级别int完全不够。洛谷这类题也经常卡这个用int会WA。完整代码已经在3.3节给出。这里补充一些实现细节dfs1里求sumW时点权和可能会很大sumW数组用long long。换根公式里的(total - 2 * sumW[v]) * w可能为负所以dp数组和中间结果全部用long long。求ans最小值时dp[i]初始可能是0但有时候题目允许全集会地点只有一个牛此时dp最小值是0答案不会是0不影响取min。只要从dp[1]开始初始化即可。如果图是链状递归深度可能到1e5下一节再说这个问题。4.4 三题横向对比题目核心考点算法复杂度易错点P1670求树的重心编号一次DFS size数组O(n)数组越界、双向建图P1395重心 所有点到重心距离和一次DFS找重心 一次DFS求深度O(n)多重心编号选择P2986带权重心最小加权距离和两次DFS 换根DPO(n)long long、换根公式从这三题能看出一条线性提升路径P1670只要求“会算worst数组”P1395多了“距离和如何快速累加”P2986则升级为“如何从任意根快速得到所有根的答案”。本质上都是那一次DFS的size数组在发挥作用。5. 刷这组题最容易踩的坑我全踩过5.1 递归爆栈问题树的题数据范围到5万、10万链状数据非常常见。C默认递归栈在编译环境里可能不够深我遇到过明明代码逻辑全对跑到一半直接stack overflow的情况。解决方案有几个手动扩栈在很多OJ上可以加这个pragma但在洛谷有时无效。改用BFS或者迭代DFS 手写栈。有些题目数据比较温柔递归加O2能过。可以先用递归写万一爆栈再改迭代至少把逻辑先跑通。我的建议是先把递归版写好本地测试通过后再考虑栈的问题因为迭代DFS写出来调试成本更高。5.2 父节点判断与数组初始化建无向图时每条边加两次递归必须传fa防止走回父节点。忘了这个DFS就会无限递归。此外如果树的下标从1开始递归前最好把sz[0]0worst[0]0。因为父节点一侧的节点数n - sz[u]在根节点处是0如果不小心把0号节点当作某个子节点也会出问题。5.3 重心不唯一的情况当某个节点的某个子节点子树大小刚好等于n/2时会出现两个相邻重心。比如一条4节点链节点2和3都是重心。P1395这类题一般要求“输出编号较小的重心”你需要在找答案时额外判断worst[i] worst[center] i center时更新center。这一行很多模板里没有漏了会WA。5.4 距离和超intP2986和P1395都算距离和。P1395如果n5万最坏距离和大约n²/4 6e8左右勉强超过int但还在long long范围。到了P2986带权结果直接可以到1e15以上。保险起见涉及距离和的变量全部用long long不要犹豫。5.5 换根公式里sumW的“全局”意义换根时用的sumW[u]是“以1为根时u子树的权值和”而不是“以当前u为新根时u子树的权值和”。这个区别很容易混淆。比如你换根到v后再递归v的子节点时sumW数组完全不用改依然用最初以1为根算出的值。理解这一点换根法就通了一半。我在第一次写P2986时换根到v后还想重新算v的子树大小结果算出来的sumW和原来不同公式一乘就错。后来才想明白sumW的作用只是用来描述“跨越这条边时两侧各有多少权值”只要第一次DFS确定了方向这个值就是固定的不需要随着根变化而重算。5.6 双向建图时vector扩容如果完全用链式前向星要开2n条边的数组经常忘。用vector则不用管。链表方式性能更好但容易越界。我一般刷洛谷用vector除非题意明确要卡常。6. 我的刷题顺序和一个小口诀如果你现在刚开始接触树的重心建议按这个顺序来先在纸上画一棵10个节点左右的树手动模拟一次DFS求sz和worst的过程彻底理解“删掉u后最大连通块”是怎么从两条路径汇总的。直接手写P1670的模板不要看题解AC为止。在模板基础上加“第二次DFS求距离和”对应P1395。把“每个节点有权值、每条边有权值”代入模型手推换根公式再写P2986。这组题我做下来最大的感受是树的重心模板本身很简单难点都在“连通块的划分”和“换根后代价怎么变”这两件事上。前者靠worst max(maxSon, n - sz[u])这一行解决后者靠dp[v] dp[u] (total - 2 * sumW[v]) * w这一行解决。两句都能默写下来大部分树形DP入门题都能应付。个人刷题时有个小技巧每道题写完AC后我会尝试把P1395的“找重心”代码改成“两次DFS 换根”再算一遍看看结果是否一致。虽然绕远了但这个对比能让你直观感受到普通重心和带权重心在实现上的区别比死记公式有用得多。多试几次以后遇到P2986的变体就不会再慌。 树的重心详解：DFS求重心、带权重心与换根DP进阶
做算法题的人应该都有体会树形结构里但凡牵扯到“删一个点”、“找一个最优位置”、“算所有点到某点的距离和”最后十有八九会落到一个东西上——树的重心。洛谷的P1670、P1395、P2986这三道题恰好是一条非常完整的进阶链路从裸模板到带权重心从“找点”到“算距离和”把它们吃透树的重心这类题基本就稳了。这篇文章我把这三道题放在一起拆核心就讲清楚三件事树的重心怎么用DFS求、带权重心和普通重心的区别在哪、换根法到底在换什么。适合已经会建图、会写最基础DFS的读者也适合准备系统性刷树论、冲击省选模板题的选手。我会把原理、代码、易错点全部摊开讲代码以C为例逻辑用Java或者其他语言照搬也没问题。1. 先搞清楚树的重心到底在求什么树的重心定义很简洁在一棵有n个节点的树里删掉某个点后剩下的森林中最大的那个连通块节点数最小。这个“删掉后最大连通块最小”的点就是树的重心。换句人话重心就是那种“你把树从它这里劈开剩下的最大一块尽量小”的点。举个例子一条长度为5的链节点1-2-3-4-5。你删掉节点3剩下的两块分别是[1,2]和[4,5]大小都是2最大是2。你删掉节点2剩下的是[1]和[3,4,5]最大是3。所以重心是3。这条链上重心甚至可能是两个当节点总数为偶数时比如节点1-2-3-4删掉2得到max(1,2)2删掉3得到max(2,1)2所以2和3都是重心。这个定义背后的直觉很实用如果你要在树上选一个地方修仓库、办集会、建立服务中心要求“最远的客户尽量近”或者“所有客户总路程尽量短”重心往往就是那个最优解。比如P1395题面里那种“在某个节点开会所有人走的路程总和最小”的需求本质就是在找重心后算距离和。树的重心有几个非常重要的性质刷题时直接当结论用重心最多有两个如果有两个它们一定相邻。以重心为根时任意子树的大小都不超过总节点数的一半。树上所有点到重心的距离之和是所有节点中最小的一组值。如果树上有边权或者点权只要把“节点数”替换成“权值”以上性质依然成立这就引出带权重心的概念。这些性质不需要死背你理解一遍DFS怎么算就记住了。下面我直接从最暴力的思路开始推看看为什么最后会收敛到那几行模板代码。2. DFS求重心原理和模板一次讲透2.1 为什么暴力做法不可行最直接的做法是枚举每个节点把它删掉然后DFS统计剩下的每个连通块大小取最大值。这样做一次统计是O(n)枚举n个点总复杂度O(n²)。题目数据规模只要到2万甚至5万立刻超时。所以必须一次DFS把所有信息算出来。关键点在于当你删掉某个节点u时剩下的连通块其实可以分成两类——一类是u的每个子节点所在的子树另一类是“u的父节点那一侧”.如果我们已经知道了以u为根时每棵子树的大小这两个部分的大小就都能算出来。这里需要先把树转成有根树。任选一个节点当根比如1号节点然后DFS一遍用size[u]表示以u为根的子树一共有多少个节点。那么u的子节点v对应的子树大小就是size[v]。u的父节点那一侧的节点数就是 n - size[u]。删掉u之后最大的连通块就是max(所有子树的size[v], n - size[u])。对每个u算出这个值取最小就找到重心了。2.2 一次DFS要记录哪些东西代码里只需要一个数组size再加上递归过程里的临时变量maxPart。递归的“后序”位置也就是先递归孩子再处理当前节点就是在做这件事递归到u时初始maxPart n - size[u]不行因为这时候父节点一侧的节点数还不知道size[u]还没完全算出来。正确顺序是先递归处理所有子节点让size[v]都有了然后再累加出size[u]最后才能用n - size[u]。这也是为什么这个DFS不能写成先处理当前节点再递归的“前序”形式必须先钻进孩子再回来汇总。我早期写过一次前序size全是0找了半天bug。2.3 模板代码#include bits/stdc.h using namespace std; const int MAXN 50005; vectorint g[MAXN]; int sz[MAXN]; // worst[u] 表示删除 u 后剩余连通块中最大的大小 int worst[MAXN]; int n; void dfs(int u, int fa) { sz[u] 1; // 先把最大连通块初始化为父节点那一侧 // 但因为此时 sz[u] 还没算完所以这里先只考虑父侧 // 准确做法是到后序位置再算 n - sz[u]目前先收集子树的 int maxSon 0; for (int v : g[u]) { if (v fa) continue; dfs(v, u); sz[u] sz[v]; maxSon max(maxSon, sz[v]); } // 后序位置此时 sz[u] 已经是完整子树大小 int parentPart n - sz[u]; worst[u] max(maxSon, parentPart); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); 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 center 1; for (int i 2; i n; i) { if (worst[i] worst[center]) { center i; } } cout center \n; return 0; }这个模板是“找编号最小的重心”。如果题目要求输出所有重心就在遍历完worst数组后把所有worst[i] worst[center]的i都输出即可。注意这里worst数组实际上只用到了“最大连通块大小”这个数值不需要真的建出森林再数节点。核心就是那句max(maxSon, n - sz[u])。这句话就是树的重心模板题的灵魂。2.4 简单验证一下拿节点1-2-3-4这条链验证。以1为根dfs(2)时先递归得到sz[3]。节点3的子树里只有4所以sz[3]2sz[4]1。节点2的maxSonsz[3]2parentPartn - sz[2]4-31所以worst[2]max(2,1)2。节点3在最外层dfs(1)里递归3的子节点4已经处理过sz[3]2maxSon1parentPart4-22所以worst[3]max(1,2)2。节点1maxSonsz[2]3parentPart0worst[1]3。worst最小是2节点2和3都是重心这个结果和前面手动推导一致。3. 从“数点”到“加权”带权重心与换根法3.1 带权重心要解决什么普通重心的每个节点权重都是1。带权重心就是每个节点有一个权值比如P2986里每个农场有c[i]头牛或者P1395里每个节点有一个人。此时“删点后最大连通块最小”的定义要改成“权值和最大的一块最小”。但注意带权问题往往是另一个形态不是“删点后最大块最小”而是“所有节点到某个点的加权距离总和最小”。这两个目标在某些问题里等价于重心但题目直接给的是后者。所以带权重心的核心考点其实是“如何在树上高效计算所有点到某个候选点的加权距离和”以及“如何从一个候选点快速得到相邻候选点的距离和”这就引出了换根法。普通重心题只要一次DFS就能做带权重心如果还是每个候选点都DFS一遍又是O(n²)。所以必须用换根DP把复杂度压到O(n)。3.2 换根法的核心转移公式假设每条边有边权w每个节点有点权val[i]。先任选一个根比如1号节点做一遍DFS求出sumW[u]以u为根的子树的权值和。total整棵树的权值和。dp[1]所有节点到1号节点的加权距离和。具体计算dp[u]的方法对孩子v的子树来说v子树的所有节点到u的距离等于它们到v的距离加上一条边w(u,v)所以dp[u] sum_{v是u的孩子} ( dp[v] sumW[v] * w(u,v) )这里的dp[v]意思是“v子树所有节点到v的加权距离和”加上sumW[v] * w就是把这些节点再往u挪一步。得到dp[1]后怎么算dp[u]这里u是任意节点而u现在是根换根的关键在于从父节点f走到子节点u跨越了边w(f,u)。想象整棵树被这条边分成两部分u这半边以及f那半边。跨过这条边后u这半边的所有节点到新根u变近了每接近w(f,u)就少一段距离总减少量就是sumW[u] * w。而f那半边的所有节点到新根u变远了总增加量就是(total - sumW[u]) * w。所以转移公式dp[u] dp[f] - sumW[u] * w (total - sumW[u]) * w dp[f] (total - 2 * sumW[u]) * w这个公式是带权重心的灵魂。它和“以1为根时每个节点子树权值和sumW[u]”绑定不管新根在哪sumW[u]都是固定的因为“以u为根的子树”在最初以1为根时就已经定义好了。3.3 代码实现#include bits/stdc.h using namespace std; const int MAXN 100005; struct Edge { int to, w; }; int n; long long val[MAXN]; long long sumW[MAXN]; long long dp[MAXN]; long long total 0; vectorEdge g[MAXN]; // 第一遍DFS求 sumW 和 dp[1] void dfs1(int u, int fa) { sumW[u] val[u]; for (auto e : g[u]) { int v e.to; int w e.w; if (v fa) continue; dfs1(v, u); sumW[u] sumW[v]; dp[1] dp[v] sumW[v] * w; // 也可以这样写 // dp[u] dp[v] sumW[v] * w; } } // 第二遍DFS换根求所有 dp void dfs2(int u, int fa) { for (auto e : g[u]) { int v e.to; int w e.w; if (v fa) continue; dp[v] dp[u] (total - 2 * sumW[v]) * w; dfs2(v, u); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n; for (int i 1; i n; i) { cin val[i]; total val[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); dfs2(1, 0); long long ans dp[1]; for (int i 2; i n; i) { ans min(ans, dp[i]); } cout ans \n; return 0; }有个细节dfs1里递归结束回到u后dp[1]累加了dp[v] sumW[v] * w但dp[v]在dfs1里的意义其实是“v子树内部所有节点到v的距离和”。这个值在下一层dfs1已经算好了。我一开始把dp数组初始化为0然后在dfs1里写成dp[u] dp[v] sumW[v] * w这样dp[u]存的是“u子树内所有节点到u的距离和”。这样做完全没问题且更容易理解。上面的代码为了简洁直接把累加放进了dp[1]你需要确保dp[1]在所有子节点都dfs完后才赋值。两种写法等价推荐写成dp[u]版本void dfs1(int u, int fa) { sumW[u] val[u]; for (auto e : g[u]) { int v e.to; int w e.w; if (v fa) continue; dfs1(v, u); sumW[u] sumW[v]; dp[u] dp[v] sumW[v] * w; } }这样dp[1]在dfs1结束后自然就是“所有节点到1的距离和”。3.4 从普通重心到带权重心的直觉变化普通重心可以认为是所有节点权值都为1的特例。你甚至可以用带权重心的代码把所有点权设为1边权设为1求出的dp数组最小值对应节点就是普通重心。而P1395其实就相当于这个特例。但反过来不行带权重心不能直接用普通重心模板因为点权和边权会改变重心的位置。P2986就是一个典型每个农场有牛、每条路有距离要使所有牛走的总路程最小这个“中心”很可能不在树的几何中心上而会偏向牛较多的农场。这也是为什么刷题顺序推荐先P1670再P2986先理解“重心是结构上的中心”再理解“给每个点加不同权重后中心会发生偏移”。4. 洛谷三题实战P1670、P1395、P2986怎么逐步升级4.1 P1670先把裸模板练熟P1670是一道最基础的模板题一般题意要求输出树的重心编号。唯一的坑可能是多组数据或者要求输出所有重心中编号较小的那个。用第2节的代码直接套即可。这道题我最初做的时候犯过一个低级错误题目没给n的数据范围我开数组太小RE了一次。给树的题数组大小至少按MAXN n 5开vector直接不用定死也行更稳妥。代码就不重复贴了用2.3节的模板把所有worst算出来后找最小即可。注意输出格式如果有两个重心有的题会要求输出编号较小的。4.2 P1395找到重心再求距离和P1395这道题通常是给定一棵树求一个节点使得所有节点到它的距离之和最小如果答案不唯一输出编号较小的点。这个题本质是普通重心距离和。先通过一次DFS找出重心然后以重心为根再做一次DFS累加所有节点深度这就是所有节点到重心的距离和。为什么重心能保证距离和最小前面说过树的重心性质所有点到重心的距离和最小。你可以这样理解如果你从重心往任意一个相邻节点挪一步跨过边后原来那一侧的k个节点到新点变远1另一侧的n-k个节点变近1总距离变化为(n-k)-k n-2k。重心满足k不超过n/2所以n-2k≥0也就是不会变好。这个性质用代码来验证更直观。这里只需要普通DFS不需要换根法因为只需要一个根的重心。// 先找到重心再用重心做DFS求距离和 #include bits/stdc.h using namespace std; const int MAXN 50005; vectorint g[MAXN]; int sz[MAXN], worst[MAXN]; int n, center, ansDist; long long sumDist 0; void dfs1(int u, int fa) { sz[u] 1; int maxSon 0; for (int v : g[u]) { if (v fa) continue; dfs1(v, u); sz[u] sz[v]; maxSon max(maxSon, sz[v]); } worst[u] max(maxSon, n - sz[u]); } void dfs2(int u, int fa, int dep) { sumDist dep; for (int v : g[u]) { if (v fa) continue; dfs2(v, u, dep 1); } } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); 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); center 1; for (int i 2; i n; i) { if (worst[i] worst[center]) center i; } // 如果有多个重心选择编号较小的这里注意题目要求 for (int i 1; i n; i) { if (worst[i] worst[center] i center) center i; } dfs2(center, 0, 0); cout center sumDist \n; return 0; }有时候P1395的题意还会要求“如果有多个重心输出编号最小的”上面已经处理了。这道题和P1670的区别就是多了个第二次DFS求深度和难度的提升不大但很关键它让你为P2986打好“距离和”的底子。4.3 P2986带权重心完整实现P2986的原题背景是奶牛集会给定n个农场每个农场的牛数量val[i]农场之间有n-1条路长度w。要求在所有农场中选一个作为集会地点让所有牛走的总路程最小输出最小总路程。这道题就是标准的带权重心用第3节的换根法。区别在于你要找的是dp数组中的最小值而不是重心本身。我在做这道题时踩过一个坑总路程可能很大要用long long。比如n10万每个点权值10万边权10万时最坏距离和是1e5 * 1e5 * 1e5 1e15级别int完全不够。洛谷这类题也经常卡这个用int会WA。完整代码已经在3.3节给出。这里补充一些实现细节dfs1里求sumW时点权和可能会很大sumW数组用long long。换根公式里的(total - 2 * sumW[v]) * w可能为负所以dp数组和中间结果全部用long long。求ans最小值时dp[i]初始可能是0但有时候题目允许全集会地点只有一个牛此时dp最小值是0答案不会是0不影响取min。只要从dp[1]开始初始化即可。如果图是链状递归深度可能到1e5下一节再说这个问题。4.4 三题横向对比题目核心考点算法复杂度易错点P1670求树的重心编号一次DFS size数组O(n)数组越界、双向建图P1395重心 所有点到重心距离和一次DFS找重心 一次DFS求深度O(n)多重心编号选择P2986带权重心最小加权距离和两次DFS 换根DPO(n)long long、换根公式从这三题能看出一条线性提升路径P1670只要求“会算worst数组”P1395多了“距离和如何快速累加”P2986则升级为“如何从任意根快速得到所有根的答案”。本质上都是那一次DFS的size数组在发挥作用。5. 刷这组题最容易踩的坑我全踩过5.1 递归爆栈问题树的题数据范围到5万、10万链状数据非常常见。C默认递归栈在编译环境里可能不够深我遇到过明明代码逻辑全对跑到一半直接stack overflow的情况。解决方案有几个手动扩栈在很多OJ上可以加这个pragma但在洛谷有时无效。改用BFS或者迭代DFS 手写栈。有些题目数据比较温柔递归加O2能过。可以先用递归写万一爆栈再改迭代至少把逻辑先跑通。我的建议是先把递归版写好本地测试通过后再考虑栈的问题因为迭代DFS写出来调试成本更高。5.2 父节点判断与数组初始化建无向图时每条边加两次递归必须传fa防止走回父节点。忘了这个DFS就会无限递归。此外如果树的下标从1开始递归前最好把sz[0]0worst[0]0。因为父节点一侧的节点数n - sz[u]在根节点处是0如果不小心把0号节点当作某个子节点也会出问题。5.3 重心不唯一的情况当某个节点的某个子节点子树大小刚好等于n/2时会出现两个相邻重心。比如一条4节点链节点2和3都是重心。P1395这类题一般要求“输出编号较小的重心”你需要在找答案时额外判断worst[i] worst[center] i center时更新center。这一行很多模板里没有漏了会WA。5.4 距离和超intP2986和P1395都算距离和。P1395如果n5万最坏距离和大约n²/4 6e8左右勉强超过int但还在long long范围。到了P2986带权结果直接可以到1e15以上。保险起见涉及距离和的变量全部用long long不要犹豫。5.5 换根公式里sumW的“全局”意义换根时用的sumW[u]是“以1为根时u子树的权值和”而不是“以当前u为新根时u子树的权值和”。这个区别很容易混淆。比如你换根到v后再递归v的子节点时sumW数组完全不用改依然用最初以1为根算出的值。理解这一点换根法就通了一半。我在第一次写P2986时换根到v后还想重新算v的子树大小结果算出来的sumW和原来不同公式一乘就错。后来才想明白sumW的作用只是用来描述“跨越这条边时两侧各有多少权值”只要第一次DFS确定了方向这个值就是固定的不需要随着根变化而重算。5.6 双向建图时vector扩容如果完全用链式前向星要开2n条边的数组经常忘。用vector则不用管。链表方式性能更好但容易越界。我一般刷洛谷用vector除非题意明确要卡常。6. 我的刷题顺序和一个小口诀如果你现在刚开始接触树的重心建议按这个顺序来先在纸上画一棵10个节点左右的树手动模拟一次DFS求sz和worst的过程彻底理解“删掉u后最大连通块”是怎么从两条路径汇总的。直接手写P1670的模板不要看题解AC为止。在模板基础上加“第二次DFS求距离和”对应P1395。把“每个节点有权值、每条边有权值”代入模型手推换根公式再写P2986。这组题我做下来最大的感受是树的重心模板本身很简单难点都在“连通块的划分”和“换根后代价怎么变”这两件事上。前者靠worst max(maxSon, n - sz[u])这一行解决后者靠dp[v] dp[u] (total - 2 * sumW[v]) * w这一行解决。两句都能默写下来大部分树形DP入门题都能应付。个人刷题时有个小技巧每道题写完AC后我会尝试把P1395的“找重心”代码改成“两次DFS 换根”再算一遍看看结果是否一致。虽然绕远了但这个对比能让你直观感受到普通重心和带权重心在实现上的区别比死记公式有用得多。多试几次以后遇到P2986的变体就不会再慌。