Hotel Assignment

Time limit2sMemory limit1024 MB

Summary

Given a tree of N hotels, choose K distinct hotels so that the sum of pairwise distances among them is maximized.

Level: Medium6 of 10
Topics: Tree, Dynamic programming
Solved: No attempts yet

Problem

The village of 경곽 has $N$ hotels and $N-1$ roads. Each road connects two distinct hotels, and any two hotels can reach each other using only roads, so the village forms a tree. The distance between two distinct hotels is the minimum number of roads that must be crossed to travel from one to the other.

One day, $K$ students from Gyeonggi Science High School came to 경곽 for a school trip. The students do not get along, so Seongho, the chief organizer of the trip, wants to assign the $K$ students to distinct hotels. To keep the students as far apart as possible, he wants to maximize the sum of distances over every pair of the $K$ assigned hotels.

Specifically, let $d(i, j)$ be the distance between the hotel assigned to student $i$ and the hotel assigned to student $j$ . You must maximize $\sum_{i=1}^{K-1}\sum_{j=i+1}^{K}d(i, j)$ . Help Seongho find the maximum value of this sum.

Input

The first line contains two integers $N$ and $K$ .

The next $N-1$ lines each contain two integers $u$ and $v$ , the numbers of the hotels connected by a road.

Output

Print the answer on the first line.

Constraints

$1 \le N \le 100\,000$
$1 \le K \le \min(N, 500)$
$1 \le u, v \le N$
The village forms a tree.

Examples2

Example 1
Input
```
5 3
1 2
1 3
2 4
2 5
```
Expected output
```
8
```
Example 2
Input
```
4 1
1 2
2 3
3 4
```
Expected output
```
0
```