납땜하기

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

소들은 이 기술로 멋진 구조물을 만들려고 한다. 구조물은 서로 연결된 $N$개($1 \le N \le 50{,}000$)의 정점과 $N-1$개의 단위 길이 간선으로 이루어진 트리이다. 각 간선은 두 정수 $A$, $B$ ($1 \le A \le N$, $1 \le B \le N$, $A \ne B$)로 주어지며, 간선 양 끝 정점의 번호를 뜻한다.

구조물을 만들려면 전선을 사야 한다. 긴 전선일수록 비싸며, 길이 $L$짜리 전선의 가격은 $L \times L$이다. 전선을 자르거나 이어 붙여 더 긴 전선으로 만들 수는 없다.

구조물의 설계도가 주어질 때, 전선들을 납땜해 구조물을 만드는 최소 비용을 구하여라.

참고로 전체 테스트 데이터의 50%는 $N < 2{,}000$을 만족한다.

• 첫째 줄에 정수 $N$이 주어진다.
• 이어지는 $N-1$개의 줄에 각 간선을 나타내는 두 정수 $A$와 $B$가 주어진다.

멋진 구조물을 만드는 데 드는 최소 비용을 한 줄에 출력한다. 정답은 32비트 정수 범위를 넘을 수 있다.

예를 들어 모든 정점이 1번 정점에 직접 연결된 성형(star) 구조에서는, 두 간선을 이어 길이 2짜리 전선 하나를 만들고 나머지 간선마다 길이 1짜리 전선을 쓰면 된다. 정점이 6개인 경우 비용은 $2^2 + 1^2 \times 3 = 7$이다.