An integer sequence \(d=(d_1,\ldots,d_N)\) is eligible for a sequence of degrees if and only if:

• \(d_i \geq 1\), and
• \(\sum_{i=1}^N d_i = 2N-2\).

Any such sequence can be a sequence of degrees, so it is sufficient to minimize the cost over such sequences.

This time, the additional cost when incrementing \(d_i\) monotonically increases as \(d_i\) increases, the problem can be solved greedily.

Specifically, first initialize as \(d_i=1\) for all \(i\), and then repeat \((N-2)\) times incrementing \(d_i\) for \(i\) with the minimal additional cost.

This greedy algorithm can be optimized using a priority_queue, resulting in running in \(\mathrm{O}(N\log N)\) time.