Australia

ウォンバットのブログ

AtCoder Regular Contest 103 F - Distance Sums

全然わからん→解説見よ→意味不明→制約見落としてた→えーん

解法

辺で繋がれたある 2頂点 u, vを考えます。辺を切ったときのそれぞれの連結成分のサイズを n_u, n_vとすると、

 D_v=D_u+n_u-n_v=D_u+N-2n_v

が成り立ちます。ここで、頂点 uを固定したとき 2n_v>Nを満たす頂点 vは高々 1つであることがわかるため、 D_u>D_vなる頂点 vは高々 1つになります。また、 D_u>D_vなる頂点 vが存在しないような頂点 uはちょうど 1つしかありません。
よって、 Dの大きい順に頂点を見ていけば、それに繋がるそれより Dが小さい唯一の頂点を定めることができます。
このようにして木が構築できなかったり、完成した木が入力の Dの値と合わなかったりしたら -1を出力します。

反省

問題文はちゃんと読みたいと思います。