木の次数列 \(d=(d_1,\ldots,d_N)\) としてあり得る整数列は以下を満たすものです。

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

（補足：この事実は、プリューファーコードを考えることで直ちに従います。または、総和の条件から \(d_i=1\) を満たす頂点が必ず存在することから、そのような頂点 \(i\) とそれ以外の頂点の辺を取り除くことを考えて、帰納法を回すことでも示せます。）

この条件を満たす任意の列は木の次数列としてあり得るので、上の条件を満たす列にたいするコストの最小値を考えればよいです。

これは、今回のコストの増加分が \(d_i\) の値に対して単調増加なことから、貪欲法を行うことで解くことが出来ます。

（補足：貪欲法の正当性は凸関数同士の畳み込みを考えれば示せます。）

具体的には、はじめ全ての \(i\) について \(d_i=1\) で初期化し、\(d_i\) を \(1\) 増やしたときのコストの増加分が最小となるような \(i\) について \(d_i\) を \(1\) 増やすことを \(N-2\) 回繰り返せばよいです。

更にこの貪欲法は priority_queue などを使うことで高速化できて、\(\mathrm{O}(N\log N)\) で動作します。