시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.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비트 정수형을 넘을 수도 있다.

예제 입력

6
1 2
1 3
1 4
1 5
1 6

예제 출력

7

힌트

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