自动搬运

查看原文

来自洛谷，原作者为

	Peanut_Tang 当花生遇到牛奶。

搬运于2025-08-24 22:19:25，当前版本为作者最后更新于2020-06-05 19:15:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意简析

给定一个 $n$ 个点的有根树，点有点权。求一个方案，把树剖成若干条链，使得：

1、每个点都属于唯一的一条链（单一个点也算一条链）；

2、一条链上的任意两点都有子孙关系；

3、所有链的点权极差之和最大。

输出这个最大值。

官方题解搬运

考虑一个DP，设：

$w_u$ 为点 $u$ 的点权；

$f_{u,0}$ 为覆盖以 $u$ 为根的子树的最大答案；

$f_{u,1}$ 为以 $u$ 为根的子树中，过 $u$ 的这条链还没有选定，但是选定了这条链上的最大值的最大答案（链上的最大值会预先加上）；

$f_{u,2}$ 为以 $u$ 为根的子树中，过 $u$ 的这条链还没有选定，但是选定了这条链上的最小值的最大答案（链上的最小值会预先减去）。

答案显然就是 $f_{1,0}$ 。

我们考虑转移，先考虑 $f_{u,1}$ ，我们分两类情况讨论（下面 $S$ 表示 $\sum_{v\in son_u} f_{u,0}$ ）：

1、 $u$ 为它所在的这条链的低端，这时 $f_{u,1}=w_u+S$ ；

2、 $u$ 不为它所在的这条链的低端，这时，若选定向儿子 $p$ 伸展，则 $f_{u,1}=S-f_{p,0}+f_{p,1}$ 。

所以我们可以得到： $f_{u,1}=S+max(w_u,max_{v\in son_u}(f_{v,1}-f_{v,0}))$ 。

类似地： $f_{u,2}=S+max(-w_u,max_{v\in son_u}(f_{v,2}-f_{v,0}))$ 。

再考虑 $f_{u,0}$ 的转移，我们仍然分两类情况讨论：

1、 $u$ 这个点是它所在的这条链的最小值，这时： $f_{u,0}=f_{u,1}-w_u$ ；

2、 $u$ 这个点是它所在的这条链的最大值，这时： $f_{u,0}=f_{u,2}+w_u$ 。

最后显然取两个最大值。

综上，时空复杂度均为 $O(n)$ ，可通过本题。