310927: CF1910F. Build Railway Stations

Monocarp is playing a computer game where he's controlling an empire. An empire consists of $n$ cities, connected by $n - 1$ roads. The cities are numbered from $1$ to $n$. It's possible to reach every city from every other one using the roads.

Traversing every road takes $2$ hours. However, that can be improved. Monocarp can build railway stations in no more than $k$ cities. After they are built, all existing roads that connect two cities with railway stations get converted to railroads and become $1$ hour to traverse.

Let $f(x, y)$ be the total time it takes to traverse the roads on the shortest path between cities $x$ and $y$.

Monocarp wants to build at most $k$ railway stations in such a way that the following value is minimized: $\sum \limits_{v=1}^{n} \sum \limits_{u=1}^{v-1} f(v, u)$ (the total time it takes to travel from every city to every other one). What the smallest value he can achieve?

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains two integers $n$ and $k$ ($2 \le k \le n \le 2 \cdot 10^5$) — the number of cities and the maximum number of railway stations Monocarp can build.

Each of the following $n-1$ lines contains two integers $v$ and $u$ ($1 \le v, u \le n$; $v \neq u$) — a road that connects cities $v$ and $u$.

It's possible to reach every city from every other one using the roads. The sum of $n$ over all testcases doesn't exceed $2 \cdot 10^5$.

For each testcase, print a single integer — the smallest total time it takes to travel from every city to every other one that Monocarp can achieve after building at most $k$ railway stations.

3
5 2
1 2
2 3
3 4
4 5
4 4
1 2
1 3
1 4
5 3
1 2
1 3
2 4
2 5

34
9
26