← 返回题目列表

Codeforces · 1910/F

F. 建造火车站

中文机器翻译题面 查看原题

Monocarp 正在玩一款电脑游戏,他正在控制一个帝国。一个帝国由 $$$n$$$ 城市组成,由 $$$n - 1$$$ 道路连接。城市编号从 $$$1$$$ 到 $$$n$$$。通过道路可以从每个城市到达每个城市。

穿越每条路需要 $$$2$$$ 小时。不过,这还可以改进。 Monocarp 可以在不超过 $$$k$$$ 的城市建造火车站。建成后,所有连接两个城市和火车站的现有道路都将改建为铁路,行驶时间将变为 $$$1$$$ 小时。

令 $$$f(x, y)$$$ 为穿过城市 $$$x$$$ 和 $$$y$$$ 之间最短路径的总时间。

Monocarp 希望以最小化以下值的方式建造最多 $$$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$$$) - Monocarp 可以建造的城市数量和最大火车站数量。

以下 $$$n-1$$$ 行均包含两个整数 $$$v$$$ 和 $$$u$$$ ($$$1 \le v, u \le n$$$; $$$v \neq u$$$) - 连接城市 $$$v$$$ 和 $$$u$$$ 的道路。

可以通过道路从其他每个城市到达每个城市。所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - Monocarp 在建造最多 $$$k$$$ 火车站后可以实现的从每个城市到每个其他城市所需的最小总时间。

示例

输入 #1

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

输出 #1

34
9
26