시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 11 3 2 100.000%

문제

소들이 전선을 가지고 놀고 있다! 소들이 익힌 납땜 기술은 한 전선의 끝 부분을 다른 전선의 중간에 붙이는 것이다.(전선의 끝과 끝을 납땜하는 것은 허용되지 않는다.) 여러 전선이 한 부분에 납땜될 수도 있다.

소들은 자신들의 납땜 기술을 이용해 멋진 구조물을 만들고자 한다. 소들이 만들고자 하는 구조물은 서로 이어진 N개(1 <= N <= 50,000)의 정점과 N-1개의 단위 길이 간선으로 이루어진다. 각 간선은 두 쌍의 정수 A와 B로 구성되며,(1 <= A <= N; 1 <= B <= N; A != B) 이는 간선 양 끝의 정점 번호를 의미한다.

소들은 구조물을 만들기 위해 전선을 구입하려고 한다. 당연하게도 긴 전선은 비싸다. 구체적으로 말하자면 길이 L짜리 전선은 L*L 가격이 든다. 안타깝게도 전선을 자르거나 붙여서 사용할 수는 없다.

구조물의 설계도가 주어질 때, 소들은 전선들을 납땜해 구조물을 가장 저렴한 비용으로 만들고자 한다. 소들을 도와 소모되는 최저비용을 계산해보자.

점수의 50%에 해당하는 테스트 데이터는 N이 2,000보다 작다.

입력

  • 첫 번째 줄: 정수 N
  • 2~N번째 줄: 각 간선을 나타내는 정수 A와 B가 차례대로 입력된다.

출력

첫 번째 줄에 멋진 구조물을 만드는데 드는 최소비용을 출력한다. 정답이 32비트 정수형을 넘을 수도 있다.

예제 입력 1

6
1 2
1 3
1 4
1 5
1 6

예제 출력 1

7

힌트

구조물의 모든 정점이 1번 정점에 연결되어 있기 때문에, 길이 2짜리 전선 하나와 길이 1짜리 전선 세 개를 구매하면 된다. 총 비용은 2*2 + 1*1 * 3 = 7이 소모된다.

W3sicHJvYmxlbV9pZCI6IjU5NzkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWIwYTlcdWI1NWNcdWQ1NThcdWFlMzAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YzE4Y1x1YjRlNFx1Yzc3NCBcdWM4MDRcdWMxMjBcdWM3NDQgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YjE4MFx1YWNlMCBcdWM3ODhcdWIyZTQhIFx1YzE4Y1x1YjRlNFx1Yzc3NCBcdWM3NzVcdWQ3OGMmbmJzcDtcdWIwYTlcdWI1NWMgXHVhZTMwXHVjMjIwXHVjNzQwJm5ic3A7XHVkNTVjIFx1YzgwNFx1YzEyMFx1Yzc1OCBcdWIwNWQgXHViZDgwXHViZDg0XHVjNzQ0IFx1YjJlNFx1Yjk3OCBcdWM4MDRcdWMxMjBcdWM3NTggXHVjOTExXHVhYzA0XHVjNWQwIFx1YmQ5OVx1Yzc3NFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuKFx1YzgwNFx1YzEyMFx1Yzc1OCBcdWIwNWRcdWFjZmMgXHViMDVkXHVjNzQ0IFx1YjBhOVx1YjU1Y1x1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NDAgXHVkNWM4XHVjNmE5XHViNDE4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC4pIFx1YzVlY1x1YjdlYyBcdWM4MDRcdWMxMjBcdWM3NzQgXHVkNTVjIFx1YmQ4MFx1YmQ4NFx1YzVkMCBcdWIwYTlcdWI1NWNcdWI0MjAgXHVjMjE4XHViM2M0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMThjXHViNGU0XHVjNzQwIFx1Yzc5MFx1YzJlMFx1YjRlNFx1Yzc1OCBcdWIwYTlcdWI1NWMgXHVhZTMwXHVjMjIwXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NCBcdWJhNGJcdWM5YzQgXHVhZDZjXHVjODcwXHViYjNjXHVjNzQ0IFx1YjljY1x1YjRlNFx1YWNlMFx1Yzc5MCBcdWQ1NWNcdWIyZTQuIFx1YzE4Y1x1YjRlNFx1Yzc3NCBcdWI5Y2NcdWI0ZTRcdWFjZTBcdWM3OTAgXHVkNTU4XHViMjk0IFx1YWQ2Y1x1Yzg3MFx1YmIzY1x1Yzc0MCZuYnNwO1x1YzExY1x1Yjg1YyBcdWM3NzRcdWM1YjRcdWM5YzQmbmJzcDtOXHVhYzFjKDEgJmx0Oz0mbmJzcDtOICZsdDs9Jm5ic3A7NTAsMDAwKVx1Yzc1OCBcdWM4MTVcdWM4MTBcdWFjZmMgTi0xXHVhYzFjXHVjNzU4IFx1YjJlOFx1YzcwNCBcdWFlMzhcdWM3NzQgXHVhYzA0XHVjMTIwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxIFx1YWMwNFx1YzEyMFx1Yzc0MCBcdWI0NTAgXHVjMzBkXHVjNzU4IFx1YzgxNVx1YzIxOCZuYnNwO0FcdWM2NDAgQlx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MThcdWJhNzAsKDEgJmx0Oz0gQSAmbHQ7PSBOOyAxICZsdDs9IEIgJmx0Oz0gTjsgQSAhPSBCKSBcdWM3NzRcdWIyOTQgXHVhYzA0XHVjMTIwIFx1YzU5MSBcdWIwNWRcdWM3NTggXHVjODE1XHVjODEwIFx1YmM4OFx1ZDYzOFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzE4Y1x1YjRlNFx1Yzc0MCBcdWFkNmNcdWM4NzBcdWJiM2NcdWM3NDQgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWM4MDRcdWMxMjBcdWM3NDQgXHVhZDZjXHVjNzg1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHViMmY5XHVjNWYwXHVkNTU4XHVhYzhjXHViM2M0IFx1YWUzNCBcdWM4MDRcdWMxMjBcdWM3NDAgXHViZTQ0XHVjMmY4XHViMmU0LiBcdWFkNmNcdWNjYjRcdWM4MDFcdWM3M2NcdWI4NWMgXHViOWQwXHVkNTU4XHVjNzkwXHViYTc0IFx1YWUzOFx1Yzc3NCBMXHVjOWRjXHViOWFjIFx1YzgwNFx1YzEyMFx1Yzc0MCBMKkwgXHVhYzAwXHVhY2E5XHVjNzc0IFx1YjRlMFx1YjJlNC4gXHVjNTQ4XHVkMGMwXHVhZTVkXHVhYzhjXHViM2M0Jm5ic3A7XHVjODA0XHVjMTIwXHVjNzQ0IFx1Yzc5MFx1Yjk3NFx1YWM3MFx1YjA5OCBcdWJkOTlcdWM1ZWNcdWMxMWMgXHVjMGFjXHVjNmE5XHVkNTYwIFx1YzIxOFx1YjI5NCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWQ2Y1x1Yzg3MFx1YmIzY1x1Yzc1OCBcdWMxMjRcdWFjYzRcdWIzYzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM4IFx1YjU0YywgXHVjMThjXHViNGU0XHVjNzQwIFx1YzgwNFx1YzEyMFx1YjRlNFx1Yzc0NCBcdWIwYTlcdWI1NWNcdWQ1NzQgXHVhZDZjXHVjODcwXHViYjNjXHVjNzQ0Jm5ic3A7XHVhYzAwXHVjN2E1IFx1YzgwMFx1YjgzNFx1ZDU1YyBcdWJlNDRcdWM2YTlcdWM3M2NcdWI4NWMgXHViOWNjXHViNGU0XHVhY2UwXHVjNzkwIFx1ZDU1Y1x1YjJlNC4gXHVjMThjXHViNGU0XHVjNzQ0IFx1YjNjNFx1YzY0MCBcdWMxOGNcdWJhYThcdWI0MThcdWIyOTQmbmJzcDtcdWNkNWNcdWM4MDBcdWJlNDRcdWM2YTlcdWM3NDQgXHVhY2M0XHVjMGIwXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcblxyXG48cD5cdWM4MTBcdWMyMThcdWM3NTggNTAlXHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCZuYnNwO1x1ZDE0Y1x1YzJhNFx1ZDJiOCZuYnNwO1x1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBOXHVjNzc0IDIsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDQ6IFx1YzgxNVx1YzIxOCBOPFwvbGk+XHJcblx0PGxpPjJ+Tlx1YmM4OFx1YzlmOCBcdWM5MDQ6Jm5ic3A7XHVhYzAxIFx1YWMwNFx1YzEyMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IEFcdWM2NDAgQlx1YWMwMCBcdWNjMjhcdWI4NDBcdWIzMDBcdWI4NWMgXHVjNzg1XHViODI1XHViNDFjXHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYTRiXHVjOWM0IFx1YWQ2Y1x1Yzg3MFx1YmIzY1x1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWIyOTRcdWIzNzAgXHViNGRjXHViMjk0IFx1Y2Q1Y1x1YzE4Y1x1YmU0NFx1YzZhOVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1Yzc3NCAzMlx1YmU0NFx1ZDJiOCBcdWM4MTVcdWMyMThcdWQ2MTVcdWM3NDQgXHViMTE4XHVjNzQ0IFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YWQ2Y1x1Yzg3MFx1YmIzY1x1Yzc1OCZuYnNwO1x1YmFhOFx1YjRlMCBcdWM4MTVcdWM4MTBcdWM3NzQgMVx1YmM4OCBcdWM4MTVcdWM4MTBcdWM1ZDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1YWUzOFx1Yzc3NCAyXHVjOWRjXHViOWFjIFx1YzgwNFx1YzEyMCBcdWQ1NThcdWIwOThcdWM2NDAgXHVhZTM4XHVjNzc0IDFcdWM5ZGNcdWI5YWMgXHVjODA0XHVjMTIwIFx1YzEzOCBcdWFjMWNcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTU4XHViYTc0IFx1YjQxY1x1YjJlNC4gXHVjZDFkIFx1YmU0NFx1YzZhOVx1Yzc0MCAyKjIgKyAxKjEgKiAzID0gN1x1Yzc3NCBcdWMxOGNcdWJhYThcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI1OTc5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU29sZGVyaW5nIiwiZGVzY3JpcHRpb24iOiI8cD5UaGUgY293cyBhcmUgcGxheWluZyB3aXRoIHdpcmVzISBUaGV5IGhhdmUgbGVhcm5lZCBhIHRlY2huaXF1ZSBjYWxsZWQgc29sZGVyaW5nLCBpbiB3aGljaCB0aGV5IGNvbm5lY3QgdHdvIHBpZWNlcyBvZiB3aXJlIHRvZ2V0aGVyIGJ5IGF0dGFjaGluZyB0aGUgZW5kcG9pbnQgb2Ygb25lIHdpcmUgdG8gYSBsb2NhdGlvbiBhbG9uZyB0aGUgbGVuZ3RoIG9mIHRoZSBvdGhlci4gKFNvbGRlcmluZyBlbmRwb2ludCB0byBlbmRwb2ludCBpcyBub3QgYWxsb3dlZC4pIFRoZXJlIGNhbiBiZSBtdWx0aXBsZSBzb2xkZXIganVuY3Rpb25zIGF0IHRoZSBzYW1lIHBvaW50LjxcL3A+XHJcblxyXG48cD5UaGUgY293cyBoYXZlIGEgcGxhbiBmb3IgYW4gQW1hemluZyBTdHJ1Y3R1cmUgdGhleSB3b3VsZCBsaWtlIHRvIGJ1aWxkLiBJdCBpcyBpbiB0aGUgZm9ybSBvZiBhIGdyYXBoIHdpdGggTiAoMSAmbHQ7PSBOICZsdDs9IDUwLDAwMCkgbm9kZXMgYW5kIE4tMSBlZGdlcyBvZiB1bml0IGxlbmd0aCBzbyB0aGF0IGVhY2ggcGFpciBvZiBub2RlcyBpcyBjb25uZWN0ZWQuIEVhY2ggZWRnZSBpcyBkZXNjcmliZWQgYnkgYSBwYWlyIG9mIGludGVnZXJzLCBBIGFuZCBCICgxICZsdDs9IEEgJmx0Oz0gTjsgMSAmbHQ7PSBCICZsdDs9IE47IEEgIT0gQikuPFwvcD5cclxuXHJcbjxwPlRoZSBjb3dzIGFyZSBhYmxlIHRvIGJ1eSB3aXJlIGZyb20gYSBsb2NhbCBzdG9yZTsgaG93ZXZlciBsb25nZXIgd2lyZSBpcyBtb3JlIGV4cGVuc2l2ZS4gSW4gcGFydGljdWxhciB0aGUgY293cyBjYW4gYnV5IGEgd2lyZSBvZiBsZW5ndGggTCB3aXRoIGNvc3QgTCpMLCBidXQgdGhleSBjYW5ub3QgY3V0IHdpcmVzIG9yIGpvaW4gd2lyZXMgdG9nZXRoZXIuPFwvcD5cclxuXHJcbjxwPkdpdmVuIHRoZSBwbGFuLCB0aGUgY293cyB3b3VsZCBsaWtlIHNvbGRlciB3aXJlcyB0b2dldGhlciB0byBidWlsZCB0aGVpciBBbWF6aW5nIFN0cnVjdHVyZS4gUGxlYXNlIGhlbHAgdGhlbSBmaW5kIHRoZSBtaW5pbXVtIHBvc3NpYmxlIGNvc3QhPFwvcD5cclxuXHJcbjxwPlRlc3QgZGF0YSB3b3J0aCBhdCBsZWFzdCA1MCUgb2YgdGhlIHBvaW50cyB3aWxsIGhhdmUgTiAmbHQ7PSAyLDAwMC48XC9wPlxyXG5cclxuPHA+UGFydGlhbCBmZWVkYmFjayB3aWxsIGJlIHByb3ZpZGVkIG9uIHlvdXIgZmlyc3QgNTAgc3VibWlzc2lvbnMgdG8gdGhpcyBwcm9ibGVtLjxcL3A+XHJcbiIsImlucHV0IjoiPHVsPlxyXG5cdDxsaT5MaW5lIDE6IEEgc2luZ2xlIGludGVnZXI6IE48XC9saT5cclxuXHQ8bGk+TGluZXMgMi4uTjogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycyBkZXNjcmliaW5nIGFuIGVkZ2U6IEEgYW5kIEI8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8dWw+XHJcblx0PGxpPkxpbmUgMTogQSBzaW5nbGUgaW50ZWdlciwgdGhlIGNvc3Qgb2Ygc29sZGVyaW5nIHRoZSB0cmVlIHRvZ2V0aGVyLiBOb3RlIHRoYXQgdGhpcyBudW1iZXIgbWF5IG5vdCBhbHdheXMgZml0IGluIGEgMzItYml0IGludGVnZXIuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IjxwPlNpbmNlIGFsbCBub2RlcyBpbiB0aGUgc3RydWN0dXJlIGFyZSBjb25uZWN0ZWQgdG8gbm9kZSAxLCB3ZSBvbmx5IG5lZWQgdG8gYnV5IG9uZSB3aXJlIG9mIGxlbmd0aCAyIGFuZCB0aHJlZSBvZiBsZW5ndGggMSwgZm9yIGEgdG90YWwgY29zdCBvZiAyICogMiArIDEgKiAxICsgMSAqIDEgKyAxICogMSA9IDcuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=