树形DP从暴力到换根：P15533那友谊连成的树95分思维

P15533 这道题是我在 MYCOI R1 里印象比较深的一道。题名“那友谊连成的树”很有画面感读完之后发现内核其实相当经典一棵 n 个点的带权树每个点上还有一个友谊值要你为每个点计算“全树的点到这个点的加权距离和”最后输出最大值。换句话说给每个点一个分数把所有成员到它这里的路程按人数加权加起来取最大。当时我状态不算好看到 n 最大 2×10^5 的时候心里咯噔一下但扫了一眼部分分设置发现前面若干子任务 n≤5000 合起来正好是 95 分。于是不纠结直接写了一个“枚举根 DFS”的暴力版把 95 分稳稳收进口袋赛后补上换根 DP 的思路才吃满最后 5 分。这篇文章就围绕这 95 分的拿法展开顺便把从 95 分到 100 分那一步的思维跳跃讲清楚。适合刚学树形 DP、想在 OI 比赛里学会“先拿部分分再优化”的选手参考。1. 先把题意和背景彻底拆开1.1 题面到底要算什么P15533 的题目描述用了不少文艺包装剥开之后其实是一个很纯粹的树上问题给一棵树有 n 个节点每条边上有一个正整数长度 w每个点有一个正整数权值 a[i]可以理解成这个点的“成员数量”定义从点 u 出发的友谊总和为 f(u) Σ a[v] · dist(u, v)dist(u, v) 是树上两点之间唯一路径的边权之和输出 max f(u)也就是要找到那个“全树所有点到它的加权距离和最大”的点。可能有人第一反应是选一个聚会点不是应该让总路程最小吗怎么这里要求最大我第一次读题也被这个方向带偏了。实际上这题故意把目标反过来了所以不少习惯往“重心”想的选手会在观察样例时愣一下。审题时这个反直觉的点是第一个坑必须踩实题目要最大不是最小。数据范围按我看到的情况是这样的前 95 分分布在若干个 n≤5000 的子任务里最后一个子任务 n≤2×10^5边权 w≤1000点权 a[i]≤100。答案会非常大必须用 long long 存。这种部分分设计经常出现在 OI 题里出题人把大部分分数故意放在小数据上就是想让即使只会暴力的选手也能拿高分。核心的计算场景其实很像日常里的“中心性”评价一个节点离其他所有节点越“远”它的这个指标反而越高。这种定义不常见但作为树形 DP 的练习非常合适因为它逼你从不同根的角度去观察同一个树。1.2 题名里的“树”不是数据结构里的树热词里能看到“字典树”“表达式树”“红黑树”“B 树”这些乱七八糟的东西但它们和 P15533 没什么关系。竞赛里说“树”基本默认是图论意义上的树n 个点、n−1 条边、无环、全连通。这道题没有任何平衡树、搜索树的操作不需要维护节点优先级也用不上字典树的 trie 节点。新手最容易犯的毛病是看到“树”字就以为自己需要学“树的遍历”以外的高级数据结构。这里给一个判断方法只要题目里说的是“给一棵树每条边有权值每个点有权值”那第一反应就应该是“邻接表 DFS”而不是去想什么高级树形结构。这题名字里的“友谊连成的树”描述的其实是一个无向连通图模型选手要在上面做全源距离加权和的统计本质是图论算法和数据结构的“树”是两码事。1.3 这题适合哪些选手参考如果刚学完树的基础遍历正愁没有题练手这个 95 分解法是很友好的一步它只需要会建图、会写递归 DFS、知道邻接表存边就能拿到绝大部分分数。如果已经开始接触树形 DP那么后面的 100 分换根 DP 部分正好补上“如何在树上把根换来自动计算答案”这个关键技能。2. 拿到题之后的思路演进暴力、部分分、正解的界限2.1 最直觉的 O(n²) 思路任何一棵树对某个固定根 u 求 f(u)最直接的办法是从 u 出发跑一次 DFS。DFS 的时候带一个参数 dep表示当前点距离根 u 已经累计走了多长每次访问到一个点 v就把 a[v] × dep 累加到以 u 为根的总和里。因为树上的路径是唯一的DFS 一路走下来得到的 dep 恰好就是 dist(u, v)。每个根跑一遍完整 DFSn 个根就是 O(n²) 次操作。这个方案不需要任何 DP 基础甚至不需要知道“子树”这个概念。你只需要保证 DFS 不会往回走递归参数里带上父节点 fa访问邻接点时跳过 fa 就行因为树没有环这么做足够防止死循环。很多人低估了这类暴力在大数据下“看起来慢实际还能跑”的程度。n5000 时n² 是 2.5×10^7现代 CPU 完成这个量级的简单运算非常轻松。题目前 95 分就放在这种规模上所以这根本不是一道“不会正解就只能拿很低分”的题而是“只要你敢写暴力就能吃下大部分分数”的题。这对比赛策略的启示比算法本身更重要。2.2 数据规模爆炸式增长时发生了什么我们可以直观感受一下 O(n²) 的开销n递归访问量级时间量级C 粗略100010^6毫秒级50002.5×10^70.1~0.5 秒1000010^81 秒左右2000004×10^10无法接受看表就明白了暴力不是“不能过”而是过不了最后那个最大的数据。出题人把 95 分放在 n≤5000 的范围内本质上是给了一个很明显的提示能拿满分的人必须在“根与根之间的答案关系”上做文章但拿 95 分的人只需要把暴力写稳。这就是部分分题的最大价值——即使你一时半会想不出更优算法也不至于被一道题直接击穿。2.3 95 分和 100 分之间到底差了什么差的不是天才而是一个观察不同根对应的答案之间有关联。举个极端例子如果 u 和 v 是相邻点那么整棵树上的点分成两拨一拨在 v 那一侧一拨在 u 这一侧。根从 u 换成 v 的时候v 侧的点离新根变近了u 侧的点离新根变远了这个“变近变远”的差值只和边权以及两侧点权有关。如果我们能先把某个初始根的答案求出来再沿着边把答案“传递”到相邻点上就可以避免为每个根从头跑一遍 DFS。这个传递过程就是换根 DP时间复杂度一下子从 O(n²) 降到 O(n)。所以 95 分和 100 分的代码量差距很小只多了一次 DFS一个换根公式。真正难的是比赛里能不能沉住气先用 95 分保底而不是一上来就硬憋满分导致代码写挂。我见过太多选手在比赛里死磕优化最后连暴力都没提交分数非常难看。3. 95 分实现枚举根 DFS3.1 建图与 DFS 框架因为 n 只有 5000邻接表直接用 vector 就能写得非常干净不需要链式前向星。链式前向前星适合追求极致常数和内存控制的场景但暴力阶段我们更该关注代码正确性和可读性。存边结构体里放两个字段目标节点 v、边权 w。struct Edge { int v; int w; }; vectorEdge g[N];DFS 的部分也很简单。用一个全局变量 cur 维护当前根下累加出来的总和每次更换根时把 cur 清零重来long long cur; void dfs(int u, int fa, long long dep) { cur a[u] * dep; for (const Edge e : g[u]) { int v e.v; if (v ! fa) { dfs(v, u, dep e.w); } } }这里的 dep 就是当前访问点到根的累计距离。因为是树不会出现“绕路”的情况DFS 第一次走到点 u 时的 dep 就是唯一路径的真实距离。不需要 visited 数组因为树没有环fa 检查已经足够。这段代码如果我提前用 n3 的小树在纸上推一下不太可能写错。3.2 完整 95 分代码下面是完整可提交版本C17 环境下直接能跑#include bits/stdc.h using namespace std; typedef long long ll; struct Edge { int v, w; }; const int N 200005; int n; ll a[N], cur; vectorEdge g[N]; void dfs(int u, int fa, ll dep) { cur a[u] * dep; for (const Edge e : g[u]) { int v e.v; if (v ! fa) { dfs(v, u, dep e.w); } } } int main() { scanf(%d, n); for (int i 1; i n; i) { scanf(%lld, a[i]); } for (int i 1; i n; i) { int u, v, w; scanf(%d%d%d, u, v, w); g[u].push_back({v, w}); g[v].push_back({u, w}); } ll res 0; for (int root 1; root n; root) { cur 0; dfs(root, 0, 0); res max(res, cur); } printf(%lld\n, res); return 0; }特别注意两点。第一主函数读入边的时候要双向加入树是无向图漏掉任意一边都会让 DFS 少遍历一个方向。第二枚举根时循环变量 root 要用来作为 DFS 的起点不能顺手把 root 改掉否则嵌套循环会乱。3.3 O(n²) 在评测时的实测表现我实际跑过 n5000 的随机树数据这个版本大概 0.1~0.3 秒就能出结果和题目给的时间限制比有很大余量。即使出题人把数据做成一条链递归深度也只有 5000 层不管是本机还是评测机都不会爆栈。这个阶段完全不需要考虑输入输出加速scanf 足够快不用加 ios::sync_with_stdio(false)也不至于 TLE。有一些人会纠结数组大小要不要开 5005 而不是 200005因为暴力只为 n≤5000 服务。我的建议是直接开大一点比如 200005反正常量内存开销可以忽略。这样做的一个额外好处是如果你在比赛里写完暴力后还想写满分代码数组不用改来改去。3.4 为什么这个版本跑不动 2×10^5前面表格已经说明n2×10^5 时 O(n²) 是 4×10^10 量级这不是“优化常数”能救回来的哪怕每次递归只做一次加法也来不及。所以最后 5 分必须换算法。看到这里如果你已经能把暴力代码写对并拿到 95 分其实已经达到了这篇文章的核心目标。剩下的问题是要不要把最后 5 分也吃掉4. 最后 5 分换根 DP 的完整做法4.1 两次 DFS 的设计思路换根 DP 的核心是“先固定一个根算一次再把答案传给相邻点”。我固定 1 号点为初始根定义两个数组sz[u]以 1 为根时u 的子树内所有点权之和dp[u]以 1 为根时u 的子树内所有点到 u 的加权距离和。第一次 DFS 自底向上算这两个数组。对某个节点 u遍历所有儿子 v先递归算出 sz[v] 和 dp[v]然后做转移sz[u] sz[v] dp[u] dp[v] sz[v] * w为什么 dp[u] 要这样转移子树 v 里所有点要先到 v总路程就是 dp[v]然后从 v 沿边走到 u子树 v 里每个点都要额外增加一段 w所以还要加上 sz[v] × w。把每个儿子的贡献加起来加上 u 自己的点权 a[u] 进入 sz[u]第一遍 DFS 就完成了。注意这里的 dp[u] 只统计了“u 的子树”并不是全树所有点到 u 的距离和。答案要的是全树范围所以必须再走第二遍 DFS把父亲那边没统计的点补进来。4.2 换根公式推导定义 ans[u] 表示全树所有点到 u 的加权距离和。初始时 ans[1] dp[1]因为以 1 为根时整棵树就是 1 的子树dp[1] 已经包含了全部点。现在假设我们已经知道 ans[u]要把根从 u 换到相邻点 v边权为 w。点集被边 (u, v) 分成两侧v 那一侧的点总权值是 sz[v]这个 sz[v] 是在以 1 为根的前提下算出来的但由于 v 本来就是 u 的儿子这个值正好就是边分割后 v 侧的权值和u 这一侧的点总权值是 sz[1] − sz[v]。原本所有点都要先到 u。换成 v 当根后v 侧每个点到 v 都比到 u 近了 w总共减少 sz[v] × wu 侧每个点到 v 都比到 u 远了 w总共增加 (sz[1] − sz[v]) × w。于是ans[v] ans[u] - sz[v] * w (sz[1] - sz[v]) * w ans[u] (sz[1] - 2 * sz[v]) * w这个公式里 sz[1] 在第一次 DFS 结束后就是全树点权总和所以第二次 DFS 里直接使用即可。如果所有点的权值都是 1那公式里的 sz 就退化成子树大小很多教材写的是 size[1] − 2 × size[v]本质一样。4.3 100 分完整代码代码和暴力版本相比只多了两个 DFS整体结构反而更像模板#include bits/stdc.h using namespace std; typedef long long ll; struct Edge { int v, w; }; const int N 200005; int n; ll a[N], sz[N], dp[N], ans[N]; vectorEdge g[N]; void dfs1(int u, int fa) { sz[u] a[u]; for (const Edge e : g[u]) { int v e.v; if (v fa) continue; dfs1(v, u); sz[u] sz[v]; dp[u] dp[v] sz[v] * e.w; } } void dfs2(int u, int fa) { for (const Edge e : g[u]) { int v e.v; if (v fa) continue; ans[v] ans[u] (sz[1] - 2LL * sz[v]) * e.w; dfs2(v, u); } } int main() { scanf(%d, n); for (int i 1; i n; i) { scanf(%lld, a[i]); } for (int i 1; i n; i) { int u, v, w; scanf(%d%d%d, u, v, w); g[u].push_back({v, w}); g[v].push_back({u, w}); } dfs1(1, 0); ans[1] dp[1]; dfs2(1, 0); ll res 0; for (int i 1; i n; i) { res max(res, ans[i]); } printf(%lld\n, res); return 0; }一定要记住在 dfs1 之后给 ans[1] 赋值再进 dfs2。我见过有人漏掉这行结果所有 ans 全是默认 0输出自然不对。另外 dfs2 只能从已经算好 ans 的父节点向儿子传播所以递归顺序是先赋值再递归下去不能反过来。4.4 验证公式的小例子自己手工验证一遍比背公式更有用。构造一条三个点的链1—2—3边权全是 1点权全是 1。手算f(1) 0×1 1×1 2×1 3f(2) 1×1 0×1 1×1 2f(3) 2×1 1×1 0×1 3最大值是 3。用换根公式从 1 换到 2ans[2] 3 (3 − 2×2)×1 2正确再从 2 换到 3ans[3] 2 (3 − 2×1)×1 3也正确。这种小例子我建议每位读者都亲自推一遍尤其是公式里那个 2×sz[v] 容易出现符号问题手算一次就能记住。4.5 两种做法的对比对比项95 分暴力100 分换根 DP时间复杂度O(n²)O(n)代码量约 50 行约 70 行核心思想枚举根重复扫描利用相邻点答案的关联性数据上限n≤5000n≤2×10^5风险点大数据超时换根公式符号写反从 95 到 100代码量增加不到 20 行难度主要在推导转移公式那一瞬间的灵光。如果比赛时间够把暴力提交保底之后静下心推导换根公式是完全来得及的。5. 调试实录与踩坑清单5.1 三个最容易出 Bug 的位置第一是 long long。点权虽然只有 100边权 1000但距离可以是 n 条边累加规模到 2×10^8 级别再乘上点权和累加 n 次轻松突破 int 上限。我的习惯是所有涉及答案和 dp 的变量一律 long long读入也直接用 %lld从源头避免。第二是换根公式的符号。第一次写 100 分代码时我把公式想反了在链数据上硬是没查出来因为链 1-2-3 点权全 1 时 f(1)f(3)对称性把错误藏住了。后来换一个不对称的树做对拍第 3 组就炸了。排查方法就是构造一个权值不对称的小树比如 1 号点权 10、2 号点权 1、3 号点权 1 的链手算再跑程序对比。第三是根的选择。第二次 DFS 一定要从第一次 DFS 的同一个根出发并且先给 ans[root] 赋值。如果两个 DFS 用了不同的根比如第一次从 1第二次从 nsz 数组的含义全乱了输出结果会莫名奇妙。5.2 本地对拍随机树生成器写完正解以后必须对拍。我写了一个简单的随机树生成脚本核心思路是新节点 i 只往编号更小的点连边这样生成出来必定是一棵树不会出现环。import random import sys n int(sys.argv[1]) print(n) print( .join(str(random.randint(1, 100)) for _ in range(n))) for i in range(2, n 1): p random.randint(1, i - 1) w random.randint(1, 1000) print(p, i, w)把暴力代码和满分代码分别编译用这个脚本生成大量随机数据跑一次 diff。做法很简单在 shell 里循环执行“生成数据 → 暴力跑 → 正解跑 → diff”。如果某组输出不一致就把 n 调小比如固定 n5再去人工分析那组数据。养成对拍习惯后树形 DP 题的正确率会明显提升。5.3 链与菊花图的特判随机数据覆盖不到两类极端结构链和菊花图。链形数据会让递归深度达到 n对栈有压力菊花图则让某个节点拥有 n−1 个儿子第一次 DFS 时 dp[1] 的计算会非常集中换根时公式里的 sz[v] 会产生极端值。我的自测组合是n3 链、n10 菊花、n200000 链各跑一遍确保不爆栈、不超时、答案合理。关于递归深度多说一句n2×10^5 的链DFS 递归 2×10^5 层在大多数 Linux 评测环境下是能正常跑完的本地 Windows 可能因为默认栈空间较小而崩溃。我自己的处理是本地调试时用编译选项扩大栈空间提交 OJ 时不管它因为评测机一般能扛住。如果你实在不放心可以把 DFS 改成显式栈迭代但竞赛中我嫌麻烦很少这么做。5.4 读入与输出的小事暴力 95 分版本用 scanf 足够。满分版本在 n2×10^5 时也只是 O(n) 规模scanf 完全够用。如果哪一天你改用 cin记得关同步ios::sync_with_stdio(false); cin.tie(nullptr);。这几个细节不致命但能避免一些莫名其妙的慢。6. 复盘与扩展从这道题学到的通用套路6.1 部分分策略不是将就这次比赛教会我最重要的一件事部分分是出题人给你的安全网。95 分的暴力版本我大概 5 分钟写完提交一次过后面所有时间都花在 100 分优化上。如果没有那个暴力打底我可能连最后的 5 分也拿不到——因为一旦正解代码写错你没有任何可以对比的基准调试时间会爆表。以后不管题目难易我都会先写一个“确保正确但可能超时”的暴力版本提交再在本地慢慢优化。看起来浪费了几分钟实际上是在给自己上保险。6.2 换根 DP 是树题里的万能骨架这套“先定根求子树信息再沿边换根迁移”的方法远不止能解这一道题。稍微变形一下就能用到很多题目上求树上所有点对距离之和先求每个子树节点到根的贡献再用换根把边两边的点对数统计出来求带权树的重心把每个点的加权距离和全部算出来取最小就是换根 DP 的典型应用求删掉一条边后两棵子树距离最小的分割方案换根时每走一条边都能顺便得到边两侧的距离指标。所以我看到树题第一反应不是“这题很难”而是“能不能用子树 dp 加换根解决”。这个思维习惯在 OI 竞赛里非常值钱。6.3 关于“树”这个概念的一点体会很多人把字典树、红黑树、表达式树这些东西混在一起其实在程序设计竞赛和工程领域里“树”这个字代表的是同一类递归结构但使用场景完全不同。P15533 这种图论树核心操作是 DFS 遍历邻接表数据结构上的树更多是插入删除和平衡维护。开始做树题时先把这两类分开能省下大量走弯路的时间。这次 95 分之后我还有一个很小的技巧分享不管题目花哨不花哨拿到手先画一棵三个点的链和一棵五个点的菊花用人工计算把最终答案推出来。这样做一方面能验证对题意的理解另一方面在代码跑完后也有一个绝对可信的测试样例。这个习惯帮我避开了至少十次低级错误比任何花哨调试工具都管用。