CF1385F Removing Leaves

给定一棵包含 $n$ 个顶点的树（无环连通图）。这棵树是无根的——也就是说，它只是一个无环的连通无向图。 每一步，你可以选择恰好 $k$ 个叶子（叶子是指只与一个其它顶点相连的顶点），这些叶子都与同一个顶点相连，并将它们以及与它们相连的边一起删除。也就是说，你可以选择叶子 $u_1, u_2, \dots, u_k$，它们都与同一个顶点 $v$ 相连（存在边 $(u_1, v)$，$(u_2, v)$，$\dots$，$(u_k, v)$），然后删除这些叶子和这些边。 你的任务是，若每一步都最优地删除叶子，求最多可以进行多少次这样的操作。 你需要回答 $t$ 组独立的测试用例。

输入的第一行包含一个整数 $t$（$1 \le t \le 2 \cdot 10^4$），表示测试用例的数量。接下来是 $t$ 组测试用例。 每组测试用例的第一行包含两个整数 $n$ 和 $k$（$2 \le n \le 2 \cdot 10^5$；$1 \le k < n$），分别表示树的顶点数和每次操作要删除的叶子数。接下来的 $n-1$ 行描述树的边。第 $i$ 行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i, y_i \le n$），表示第 $i$ 条边连接的两个顶点。保证给定的边集构成一棵树。 保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$（$\sum n \le 2 \cdot 10^5$）。

对于每组测试用例，输出一个整数，表示最多可以进行多少次操作。

下图对应第一个样例：  你可以在第一次操作中删除顶点 $2$、$5$ 和 $3$，第二次操作中删除顶点 $1$、$7$ 和 $4$。 下图对应第二个样例：  你可以在第一次操作中删除顶点 $7$、$8$ 和 $9$，第二次操作中删除顶点 $5$、$6$ 和 $10$，第三次操作中删除顶点 $1$、$3$ 和 $4$。 下图对应第三个样例：  你可以在第一次操作中删除顶点 $5$ 和 $7$，第二次操作中删除顶点 $2$ 和 $4$，第三次操作中删除顶点 $1$ 和 $6$。 由 ChatGPT 4.1 翻译