这个题做完才发现是 APIO2021T3 的原题，感觉当时被这套题干爆的时候还近在眼前。
考虑确定 \(x\) 的话有一个比较显然的 dp + 排序后贪心的 \(O(n\log n)\) 解法。
我们考虑如果一条边 \((u,v)\)，在 \(x\ge \max\{deg_u,deg_v\}\) 之后就不会删了；如果 \(x\le \min\{deg_u,deg_v\}\) 那我们保留这条边；这样 \(n\) 个时刻的连通块大小显然还是 \(O(n)\) 的，问题就在于介于 \(\min,\max\) 之间，这个时候是一个存在的点挂了一个限制已经无所谓的叶子。
考虑对连通块的每个点做树形 dp，用数据结构维护每个点挂着的额外的叶子（按照 weight 排序），然后合并的时候我们需要一个和额外挂着的叶子的数量无关的做法。
考虑实际上是把两个序列归并起来：一个序列是额外的叶子，一个序列是所有的儿子。
第二个序列的大小是可以接受的，所以我们在他上面二分出到底要选多少个，这样的话我们的数据结构只需要支持 k-th prefix sum 还有 \(\le x\) 的值的个数两个东西，用平衡树去维护即可。
这样时间复杂度是 \(O(n\log^2 n)\) 的。