记录【P2986 [USACO10MAR] Great Cow Gathering G】

传送门。

$\texttt{Description}$

给定一个棵带权树，点权为 $c_i$，定义一个点 $u$ 到 $X$ 的不方便程度为 $c_u$ 乘 $u$ 到 $X$ 的距离。

选择一个点，使得所有点到这个点的不方便程度之和最小。

$1\le n\le 10^5$。

$\texttt{Solution}$

非常显然的树形 DP。

设 $f_i$ 表示所有点到 $i$ 的不方便程度之和。则答案为 $\min_{1\le i\le n}\{f_i\}$。

考虑转移。

设 $g_i$ 表示以 $i$ 为根的子树中，所有点到 $i$ 的不方便程度之和。

考虑 $u$ 的儿子 $v$，$f_v$ 首先应加上 $g_v$。这是 $v$ 子树的贡献。

然后应该加上 $u$ 子树的贡献，即 $f_u$，但发现在 $v$ 子树中算重，应该再减掉 $v$ 的贡献，即 $g_v$。 

我们发现还是有一部分会被多算，即 $u,v$ 之间的长度，所以再应减去 $sum_v\times w$，其中 $sum_i$ 表示子树 $i$ 中所有点的点权和。

但是 $u,v$ 这条边应该被放在以 $v$ 为根时 $u$ 子树每个点的贡献里，所以应该加上 $(S-sum_v)\times w$。

可能说的有点绕……不过个人感觉换根 $\texttt{DP}$ 重点在于画图。

最终转移方程为 $f_v=f_u+w\times(S-2\times sum_v)$。（移项之后）