自动搬运

查看原文

来自洛谷，原作者为

	墨舞灵纯 Belief triggers the power to do.♡

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

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

以下是正文

为什么$prufer$序的好题现存的题解里面没提到$prufer$序的作用啊。。那我来造福社会。。

根据$prufer$序的性质，对于一个度数为 $x$ 的点肯定在$prufer$序中出现了 $x-1$ 次。

考虑 $dp$ 设$f[i]$表示总度数为 $i$ 可以得到的最大价值，则相当于体积为 $x-1$ ，价值为 $d(x)$ 的物品做完全背包。

但是我们考虑体积为 $0$ 的它也有价值，于是考虑先把所有 $0$ 体积的扔进背包里面，然后做的时候替换掉这些体积为 $0$ 的，其实相当于把 $d(x)-d(1)$ 当成新权值来搞就行了。

这个$dp$是$O(n^2)$的。

然后就是输出方案，在$dp$的时候记一下这个方案是由哪个方案转移过来的，然后既然知道每个结点度数那就肯定能根据$prufer$序还原出来原来的树，贪心构树即可，理论上可以做到$O(nlogn)$。

代码也不难写，讲一下实现过程：

1 . 预处理对于每个$x$对应的 $d(x)$

2 . $f[0]=n \times d[1]$，表示总度数和为$0$的最大价值

3 . 更新的时候直接用完全背包更新并且记录这个状态是由前面的哪个状态得来的

4 . 从$n-2$开始一个个跳前驱把所有的可能度数记下来并且排序

5 . $dfs$一下$prufer$序构树的过程顺便输出

不贴代码了，看了这个实现过程还不会写的。。请D我吧是我讲的不好对不起