次数が \(1\) となる頂点の個数に着目します。最初星が \(M\) 個のとき、そのような頂点は \(N-M\) 個あります。また操作によって次数が \(1\) の頂点 \(2\) つが次数 \(2\) となるので、終了時の木には \(N-3M+2\) 個あります。よって \(M\) の値は簡単に求められます。

また、操作によって次数が \(1\) の頂点 \(2\) つが次数 \(2\) となるので、終了時の木における次数を大きい順に \(M\) 個取れば、それが開始前の状況において星の真ん中の頂点の次数に対応します。

以上より次数列を sort することがボトルネックとなり \(O \left( N \log N \right)\) で解けます。頻度を持つことで \(O \left( N \right)\) でも解けます。

実装例