Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

F. Постройте вокзалы
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в компьютерную игру, в которой он управляет империей. Империя состоит из $$$n$$$ городов, соединенных $$$n - 1$$$ дорогой. Города пронумерованы от $$$1$$$ до $$$n$$$. Из каждого города можно добраться до любого другого по дорогам.

Поездка по одной дороге занимает $$$2$$$ часа. Однако, это можно улучшить. Монокарп может построить вокзалы в не более чем $$$k$$$ городах. После того, как они построены, все существующие дороги, которые соединяют два города с вокзалами, превращаются в железные дороги, поездка по которым занимает $$$1$$$ час.

Пусть $$$f(x, y)$$$ будет суммарным временем, которое потребуется, чтобы проехать по дорогам на кратчайшем пути между городами $$$x$$$ и $$$y$$$.

Монокарп хочет построить не более $$$k$$$ вокзалов таким образом, чтобы минимизировать следующее значение: $$$\sum \limits_{v=1}^{n} \sum \limits_{u=1}^{v-1} f(v, u)$$$ (суммарное время, необходимое, чтобы добраться из каждого города до каждого другого города). Какое наименьшее значение он может получить?

Входные данные

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

Во первой строке каждого набора входных данных записаны два целых числа $$$n$$$ и $$$k$$$ ($$$2 \le k \le n \le 2 \cdot 10^5$$$) — количество городов и максимальное количество вокзалов, которые может построить Монокарп.

В каждой из следующих $$$n-1$$$ строк записаны два целых числа $$$v$$$ и $$$u$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$) — дорога, соединяющая города $$$v$$$ и $$$u$$$.

Из каждого города можно добраться до любого другого по дорогам. Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

На каждый набор входных данных выведите одно целое число — наименьшее суммарное время, необходимое, чтобы добраться из каждого города до каждого другого города, которое Монокарп может получить, если построит не более $$$k$$$ вокзалов.

Пример
Входные данные
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