题解 P6293 【[eJOI2017]经验】

· · 题解

题意简析

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

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

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

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

输出这个最大值。

官方题解搬运

考虑一个DP，设：

$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)$ ，可通过本题。