Let \(d_1,d_2,\cdots,d_N\) be the degrees of the vertices, where each value is decreased by \(1\).

For each \(0 \leq s \leq N-2\), let \(m(s)\) and \(M(s)\) be the minimum and maximum sizes of a subset of \(d_i\) whose sum is \(s\), respectively. (If there is no such subset, let \(m(s)=\infty,M(s)=-\infty\) for convenience.) Then, the following property holds:

• For every \(m(s) \leq c \leq M(s)\), it is possible to choose \(c\) elements from \(d\) whose sum is \(s\).

If we accept this, the problem is easy to solve. Consider finding \(m(s)\) with DP. Because there are at most \(O(\sqrt{N})\) different values in \(d\), we can classify the elements according to the values and use the sliding window algorithm for each value to accelerate the transitions, finding \(m(s)\) in \(O(N \sqrt{N})\) time. Then, \(M(s)\) can be immediately found from \(m(s)\). Therefore, we can solve the problem in \(O(N \sqrt {N})\) time.

Finally, we will prove the property we assumed above.

Let \(z\) be the number of \(0\)s in \(d\). We are done if we show \(M(s)-m(s) \leq 2z\). This is because a solution achieving \(M(s)\) always uses \(z\) \(0\)s, and a solution achieving \(m(s)\) always uses no \(0\)s.

Incidentally, for any subset \(x\) of \(d\), we have \(-z \leq s-c \leq z-2\), where \(c\) and \(s\) are the size and sum of \(z\), respectively. This is because the sum of \(d_i-1\) such that \(d_i-1<0\) is \(-z\), and the sum of \(d_i-1\) such that \(d_i-1>0\) is \(z-2\). Then, it follows from \(-z \leq s-M(s) \leq s-m(s) \leq z-2\) that \(M(s)-m(s) \leq 2z\), completing the proof.