考虑暴力，单独考虑一个度数限制\(d\)
令\(f_{i,0/1}\)为\(i\)子树全部满足限制，\((fa_i,i)\)是否被割断的最小值
若不考虑\(u\)这个点的度数限制，\(f_{u,0/1}=\sum\limits_{v\in son_u}min(f_{v,0},f_{v,1}+(u,v).w)\)
再考虑进\(u\)这个点，若\(f_{v,1}+(u,v).w\le f_{v,0}\)显然会选择割断，令\(cnt_u\)为这样的个数
若\(deg_u-cnt_u\le d\)则无需操作
若\(deg_u-cnt_u>d\)，则还需要选择\(deg_u-cnt_u-d\)个点割掉，可以对差值\(f_{v,1}+(u,v).w-f_{v,0}\)建堆，最后留在堆中的，为需要割断的边
考虑优化这个暴力，若枚举\(d=1\sim n-1\)
对于\(deg_u\le d\)，可以从这个图中移去，顺便将\((u,v).w\)加入点\(v\)的堆中，以示割掉这条边为限制度数
对于一个点，需要割断的边数是递减的，堆内虚边的数量若大于其，则永久弹出一些
则每次从堆内弹出的次数与实边的数量相关
这样做的复杂度为\(O(nlogn)\)
原文：https://www.cnblogs.com/Grice/p/12925820.html