410481: GYM104025 G Get off work

To improve the commuting efficiency of employees, Master Yi's company has planned a new shuttle operation plan. The office location and the home of its employees are like a tree with $$$n$$$ nodes where the vertex $$$1$$$ is the company as well as the root of the tree, and each of the other nodes is the home of an employee.

The company plans to use several shuttles, which will depart from the company in all directions without turning back, and a shuttle bus has only $$$k$$$ seats for employees. The employee immediately gets off the bus and goes home when the bus reaches the node of his/her home. To save money, please help them calculate the minimum number of shuttles needed to take all company employees home after work.

The first line contains a single integer $$$t\ (1\le t\le 10^4)$$$, the number of test cases. For each test case:

The first contains $$$2$$$ integers $$$n\ (2\le n\le 2 \cdot 10^5)$$$ and $$$k\ (1\le k\le 50)$$$, which shows the number of nodes and the number of seats on each bus.

The next $$$n−1$$$ lines show the edges of the tree — one edge per line. Each line contains two integers $$$u,v\ (1\le u,v\le n;u\neq v)$$$ representing an edge.

It is guaranteed that the given edges form a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

For each test case, print a single integer, which shows the minimum number of shuttles needed.

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

3

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

3

Fig. 1. the tree in the example

We can send $$$5$$$ employees off with $$$3$$$ shuttles, here is an optimal arrangement.

• The first bus goes from the root node to node $$$4$$$, and the employees who live in nodes $$$2$$$ and $$$4$$$ sit on this bus.
• The second bus goes from the root node to node $$$5$$$, and the employee who lives in node $$$5$$$ sits on this bus.
• The third bus goes from the root node to node $$$6$$$, and the employees who live in node $$$3$$$ and node $$$6$$$ sit on this bus.