P2986 [USACO10MAR] Great Cow Gathering G 分析 & 换根 DP

· · 个人记录

一眼树形 DP，但是不太好处理，因为根是不确定的。

我们可以先假设点 1 是根（因为题目保证联通），然后预处理出一些参数：\sigma 和 s。\sigma(u) 表示点 u 的子树中的点权乘上边权和，s(u) 表示点 u 为根的子树节点数量。

然后我们知道：\sigma(1) 就是以点 1 为根时题目要求的权值和。但是，我们现在要求的是以其他点为根时的权值和。

这实际上是可以根据计算出来的参数得到的。

我们设 f(v) 表示点 v 为根时，题目要求的权值的和。设点 u 是点 v 在以点 1 为根时的父节点，w 是树边 (u,v) 的权值，那么我们可以得到这样的转移方程：

f(v) = f(u) - ws(v) + w\times(T - s(v))

之后我们取得 f 在 [1, n] 上的最小值即可。

这叫做换根 DP，基本策略是：