本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-01-14 12:54:22

一眼树形 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，基本策略是：

• 先假设某一个点为根，算得一些参数
• 推出转移方程，算出其他点为根时的值
• 取最值