题解 P5454 【[THUPC2018]城市地铁规划】

· · 题解

为什么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我吧是我讲的不好对不起