全然わからん→解説見よ→意味不明→制約見落としてた→えーん
解法
辺で繋がれたある頂点
を考えます。辺を切ったときのそれぞれの連結成分のサイズを
とすると、
が成り立ちます。ここで、頂点を固定したとき
を満たす頂点
は高々
つであることがわかるため、
なる頂点
は高々
つになります。また、
なる頂点
が存在しないような頂点
はちょうど
つしかありません。
よって、の大きい順に頂点を見ていけば、それに繋がるそれより
が小さい唯一の頂点を定めることができます。
このようにして木が構築できなかったり、完成した木が入力のの値と合わなかったりしたら
を出力します。
反省
問題文はちゃんと読みたいと思います。
