CF1119F Niyaz and Small Degrees - Solution

· · 题解

开个玩笑，但确实远没 *3400 这么难。

不妨先来考虑怎么相对快地求出一个 x 的答案。

设 f_u 为 u 子树内所有点度数删到 \le x 的删边最小代价，g_u 为 u 子树内除 u 之外度数都删到 \le x，但是 u 的度数恰好为 x + 1 的删边最小代价。

那么对于 v \in \text{child}(u)，将一个 g_v 纳入考虑意味着 (u,\,v) 必删，否则 (u,\,v) 删或不删均可。

令 t = deg_u，为了求 f_u 我们要删除 t - x 条边，求 g_u 要删除 t - x - 1 条边。

如果一个点在被删除的范围之外，那么它只能取 f，否则可以取 g（我们令 h \gets \min(f,\,g) 则一定取 h）。

于是我们按 w(u,\,v) + h - f 升序排序选取删边即可。

复杂度 \Theta(n \log n)。

接下来考虑怎么做 x = 1 \dots n。我们知道 \sum deg_i = 2(n - 1)，而度数本身就小于等于 x 的点我们当然是不用考虑它们的合法性的，我们直接对度数 > x 的点建立虚树，那么显然是可以根据上面的东西 dp 的。

于是做完了，时间复杂度 $\Theta(n \log n)$。 哦还没那么简单，你需要对 $deg_v < x,\,w(u,\,v)$ 和虚树上的结点跑一个归并，我们直接枚举虚树上 $u$ 的子结点然后直接插入到前者里面，也就是每个结点开个权值线段树维护一下前缀和（具体的话每次 $x$ 增加是对被踢出去的结点的父亲做单点删除），复杂度 $\Theta(n \log V)$，真做完了。