代码修改 题解

· · 个人记录

原题：CF1119F

由于出题人水平不够，比赛急需一道T4，便出此下策搬运了一道CF原题。

没想到竟然和APIO的一道原题撞了（两道题的出题人似乎是同一个人），如果大家有做过原题，十分抱歉让大家体验不好，在此郑重道歉，大家可以当三倍经验提交。

本题很显然是一道树形dp。首先我们考虑对于每个固定的x计算答案。设f[i][0/1]表示i向其父亲连的边删或不删时的最小代价。考虑暴力，假定i和他儿子连接的所有边都不删，我们发现一共需要删掉的边最少deg[i]-x条，那么就相当于选择所有儿子中f[j][0]+w(i,j)-f[j][1]最小的deg[i]-x个删掉，这个过程用堆维护，时间复杂度O(n^2\log n)。

考虑正解。如果从小到大考虑每个x，那么一个deg=x的点对[x,n-1]是没有贡献的，对于每个点只需考虑x<deg的情况，这样的量级是\sum deg=n的。我们对于每个点都维护一个堆，从小到大枚举x，每次找出这样的点i，因为它已经合法所以可以把它直接删除，但它连的边可能还有用,我们直接把这条边的边权塞进j的大根堆中，这个堆就维护最优的删边方案，如果大小足够就把堆顶弹出即可。

然后原图就分成了若干个连通块，我们对于每个连通块分别dp即可，考虑j的转移时也把选择边(i, j)的代价塞进堆中，然后用堆决策即可。注意dp之后还要还原堆，这时候就需要堆支持删除操作。注意每次跑完一个点后需要还原这个点的堆，也就是堆中只保留其他度数不超过x的点到这个点的距离。所以维护两个堆实现可删除堆即可。dp的时候注意只能访问度数大于等于x的点，所以我们要把每个点的边按终点的度数大小排序。因为每个点只会被dp度数次，所以总时间复杂度是度数的累加，时间复杂度O(n log n)

更详细的解释可以参考这位大佬的题解