호텔 배정 timer 2s memory 1024MB

경곽 마을은 N개의 호텔과 N-1개의 길로 이루어져 있다. 하나의 길은 서로 다른 두 호텔을 연결하며, 임의의 서로 다른 두 호텔을 길만 사용하여 오갈 수 있다. 즉, 경곽 마을은 트리 구조를 이룬다. 서로 다른 두 호텔 사이의 거리는 한 호텔에서 다른 호텔로 가기까지 지나야 할 길의 개수의 최솟값으로 정의된다.

어느 날, K명의 경기과고 학생이 경곽 마을로 수학여행을 왔다. 경기과고 학생들은 서로 사이가 좋지 않기 때문에, 수학여행의 총책임자 성호는 K명의 학생을 서로 다른 호텔에 배정하고자 한다. 또 학생들을 최대한 멀리 떨어뜨려 놓기 위해, 학생들에게 배정된 K개의 호텔 중 서로 다른 두 호텔을 선택하는 모든 방법에 대한 두 호텔 사이의 거리의 총합을 최대화하고자 한다.

구체적으로, d(i, j)를 i번 학생과 j번 학생에게 배정된 호텔 사이의 거리라 할 때, \sum_{i=1}^{K-1}\sum_{j=i+1}^{K}d(i, j)를 최대화해야 한다. 성호를 도와 이 값의 최댓값을 구해 주자.