30100번 - 호텔 배정

문제

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

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

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

입력

첫째 줄에 두 정수 $N$과 $K$가 주어진다.

이후 $N-1$개의 줄에 마을의 길이 연결하는 호텔의 번호를 나타내는 두 정수 $u, v$가 주어진다.

출력

문제의 정답을 첫 줄에 출력한다.

제한

• 1ドル \le N \le 100,000円$
• 1ドル \le K \le \min(N, 500)$
• 1ドル \le u, v \le N$
• 마을이 트리 구조를 이룬다.

힌트