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