You are given a tree (connected graph without cycles) consisting of $n$ vertices. The tree is unrooted — it is just a connected undirected graph without cycles.

In one move, you can choose exactly $k$ leaves (leaf is such a vertex that is connected to only one another vertex) connected to the same vertex and remove them with edges incident to them. I.e. you choose such leaves $u_1, u_2, \dots, u_k$ that there are edges $(u_1, v)$, $(u_2, v)$, $\dots$, $(u_k, v)$ and remove these leaves and these edges.

Your task is to find the maximum number of moves you can perform if you remove leaves optimally.

You have to answer $t$ independent test cases.


-----Input-----

The first line of the input contains one integer $t$ ($1 \le t \le 2 \cdot 10^4$) — the number of test cases. Then $t$ test cases follow.

The first line of the test case contains two integers $n$ and $k$ ($2 \le n \le 2 \cdot 10^5$; $1 \le k < n$) — the number of vertices in the tree and the number of leaves you remove in one move, respectively. The next $n-1$ lines describe edges. The $i$-th edge is represented as two integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le n$), where $x_i$ and $y_i$ are vertices the $i$-th edge connects. It is guaranteed that the given set of edges forms a tree.

It is guaranteed that the sum of $n$ does not exceed $2 \cdot 10^5$ ($\sum n \le 2 \cdot 10^5$).


-----Output-----

For each test case, print the answer — the maximum number of moves you can perform if you remove leaves optimally.


-----Example-----
Input
4
8 3
1 2
1 5
7 6
6 8
3 1
6 4
6 1
10 3
1 2
1 10
2 3
1 5
1 6
2 4
7 10
10 9
8 10
7 2
3 1
4 5
3 6
7 4
1 2
1 4
5 1
1 2
2 3
4 3
5 3

Output
2
3
3
4



-----Note-----

The picture corresponding to the first test case of the example:

[Image]

There you can remove vertices $2$, $5$ and $3$ during the first move and vertices $1$, $7$ and $4$ during the second move.

The picture corresponding to the second test case of the example:

[Image]

There you can remove vertices $7$, $8$ and $9$ during the first move, then vertices $5$, $6$ and $10$ during the second move and vertices $1$, $3$ and $4$ during the third move.

The picture corresponding to the third test case of the example:

$\text{of}$

There you can remove vertices $5$ and $7$ during the first move, then vertices $2$ and $4$ during the second move and vertices $1$ and $6$ during the third move.

Difficulty: HARD
Tags: Tree algorithms

Data structures

Implementation

Greedy algorithms
Skill types: Data structures

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
for f in range(int(input())):
	(n, k) = map(int, input().split())
	neig = [0] * n
	for i in range(n):
		neig[i] = [0]
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		a -= 1
		b -= 1
		neig[a][0] += 1
		neig[b][0] += 1
		neig[a].append(b)
		neig[b].append(a)
	conleaves = [0] * n
	for i in range(n):
		conleaves[i] = [0]
	goodvertices = []
	mx = 0
	for i in range(n):
		if neig[i][0] == 1:
			if neig[neig[i][1]][0] > 0:
				conleaves[neig[i][1]][0] += 1
				conleaves[neig[i][1]].append(i)
				neig[i][0] = 0
				if conleaves[neig[i][1]][0] == k:
					goodvertices.append(neig[i][1])
	while len(goodvertices) > 0:
		v = goodvertices.pop()
		rem = conleaves[v][0] // k
		mx += rem
		rest = conleaves[v][0] % k
		conleaves[v] = conleaves[v][0:rest + 1]
		conleaves[v][0] = rest
		neig[v][0] -= rem * k
		if neig[v][0] == 1:
			for i in range(1, len(neig[v])):
				if neig[neig[v][i]][0] > 0:
					neig[v][0] = 0
					conleaves[neig[v][i]][0] += 1
					conleaves[neig[v][i]].append(v)
					if conleaves[neig[v][i]][0] == k:
						goodvertices.append(neig[v][i])
	print(mx)


from sys import stdin, gettrace
if gettrace():
	inputi = input
else:

	def input():
		return next(stdin)[:-1]

	def inputi():
		return stdin.buffer.readline()

def readGraph(n, m):
	adj = [set() for _ in range(n)]
	for _ in range(m):
		(u, v) = map(int, input().split())
		adj[u - 1].add(v - 1)
		adj[v - 1].add(u - 1)
	return adj

def readTree(n):
	return readGraph(n, n - 1)

def solve():
	(n, k) = map(int, input().split())
	adj = readTree(n)
	if k == 1:
		return (n - 1, n, k)
	leaves = {}
	lc = [0] * n
	for i in range(n):
		if len(adj[i]) == 1:
			lc[adj[i].pop()] += 1
			lc[i] = -1
	st = [i for i in range(n) if lc[i] >= k]
	res = 0
	while st:
		i = st.pop()
		res += lc[i] // k
		if len(adj[i]) == lc[i] + 1 and lc[i] % k == 0:
			for a in adj[i]:
				if lc[a] != -1:
					lc[a] += 1
					if lc[a] == k:
						st.append(a)
			lc[i] = -1
		else:
			lc[i] %= k
	return (res, n, k)

def main():
	printproblem = False
	t = int(input())
	for i in range(t):
		(res, _, _) = solve()
		print(res)
main()


from collections import defaultdict
import sys, math
f = None
try:
	f = open('q1.input', 'r')
except IOError:
	f = sys.stdin
if 'xrange' in dir(__builtins__):
	range = xrange
sys.setrecursionlimit(10 ** 6)

def print_case_iterable(case_num, iterable):
	print('Case #{}: {}'.format(case_num, ' '.join(map(str, iterable))))

def print_case_number(case_num, iterable):
	print('Case #{}: {}'.format(case_num, iterable))

def print_iterable(A):
	print(' '.join(A))

def read_int():
	return int(f.readline().strip())

def read_int_array():
	return [int(x) for x in f.readline().strip().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def read_string():
	return list(f.readline().strip())

def ri():
	return int(f.readline().strip())

def ria():
	return [int(x) for x in f.readline().strip().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def rs():
	return list(f.readline().strip())

def bi(x):
	return bin(x)[2:]
from collections import deque
import math
NUMBER = 10 ** 9 + 7

def factorial(n):
	M = NUMBER
	f = 1
	for i in range(1, n + 1):
		f = f * i % M
	return f

def mult(a, b):
	return a * b % NUMBER

def minus(a, b):
	return (a - b) % NUMBER

def plus(a, b):
	return (a + b) % NUMBER

def egcd(a, b):
	if a == 0:
		return (b, 0, 1)
	else:
		(g, y, x) = egcd(b % a, a)
		return (g, x - b // a * y, y)

def modinv(a):
	m = NUMBER
	(g, x, y) = egcd(a, m)
	if g != 1:
		raise Exception('modular inverse does not exist')
	else:
		return x % m

def choose(n, k):
	if n < k:
		assert false
	return mult(factorial(n), modinv(mult(factorial(k), factorial(n - k)))) % NUMBER
from collections import deque, defaultdict
import heapq
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc

def dfs(g, timeIn, timeOut, depths, parents):
	cnt = 0
	stack = [[1, 0, 0, 0]]
	while stack:
		(v, neig_i, parent, depth) = stack[-1]
		parents[v] = parent
		depths[v] = depth
		if neig_i == 0:
			timeIn[v] = cnt
			cnt += 1
		while neig_i < len(g[v]):
			u = g[v][neig_i]
			if u == parent:
				neig_i += 1
				continue
			stack[-1][1] = neig_i + 1
			stack.append([u, 0, v, depth + 1])
			break
		if neig_i == len(g[v]):
			stack.pop()
			timeOut[v] = cnt
			cnt += 1
cnt = 0

@bootstrap
def dfs(v, adj, timeIn, timeOut, depths, parents, parent=0, depth=0):
	global cnt
	parents[v] = parent
	depths[v] = depth
	timeIn[v] = cnt
	cnt += 1
	for u in adj[v]:
		if u == parent:
			continue
		yield dfs(u, adj, timeIn, timeOut, depths, parents, v, depth + 1)
	timeOut[v] = cnt
	cnt += 1
	yield

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def get_num_2_5(n):
	twos = 0
	fives = 0
	while n > 0 and n % 2 == 0:
		n //= 2
		twos += 1
	while n > 0 and n % 5 == 0:
		n //= 5
		fives += 1
	return (twos, fives)

def shift(a, i, num):
	for _ in range(num):
		(a[i], a[i + 1], a[i + 2]) = (a[i + 2], a[i], a[i + 1])

def equal(x, y):
	return abs(x - y) <= 1e-09

def getAngle(a, b, c):
	ang = math.degrees(math.atan2(c[1] - b[1], c[0] - b[0]) - math.atan2(a[1] - b[1], a[0] - b[0]))
	return ang + 360 if ang < 0 else ang

def getLength(a, b):
	return math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)
from heapq import heapify, heappush, heappop

def bfs(adj):
	s = set()
	d = defaultdict(set)
	q = deque([])
	s.add(0)
	d[0].add(0)
	q.append((0, 0))
	while len(q) > 0:
		(v, depth) = q.popleft()
		for u in adj[v]:
			if u not in s:
				s.add(u)
				d[depth + 1].add(u)
				q.append((u, depth + 1))
	return d

def solution(adj, n, k):
	if k == 1:
		return n - 1
	if n == 2:
		return 0
	leaves = [set() for i in range(n)]
	stack = []
	for v in range(n):
		if len(adj[v]) == 1:
			leaves[adj[v].pop()].add(v)
	for v in range(n):
		if len(leaves[v]) >= k:
			stack.append(v)
	cnt = 0
	while len(stack) > 0:
		cnt += 1
		v = stack.pop()
		ls = set()
		try:
			for i in range(k):
				ls.add(leaves[v].pop())
		except:
			return f'{cnt}000{n}000{k}'
		adj[v] -= ls
		if len(adj[v]) == 0:
			continue
		elif len(adj[v]) == 1:
			u = adj[v].pop()
			leaves[u].add(v)
			if len(leaves[u]) == k:
				stack.append(u)
		elif len(leaves[v]) >= k:
			stack.append(v)
	return cnt

def main():
	T = 1
	T = ri()
	for i in range(T):
		(n, k) = ria()
		adj = [set() for _ in range(n)]
		for _ in range(n - 1):
			(a, b) = ria()
			a -= 1
			b -= 1
			adj[a].add(b)
			adj[b].add(a)
		x = solution(adj, n, k)
		if 'xrange' not in dir(__builtins__):
			print(x)
		else:
			(print >> output, str(x))
	if 'xrange' in dir(__builtins__):
		print(output.getvalue())
		output.close()
if 'xrange' in dir(__builtins__):
	import cStringIO
	output = cStringIO.StringIO()
main()


import sys

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s)
	sys.stdout.write('\n')

def wi(n):
	sys.stdout.write(str(n))
	sys.stdout.write('\n')

def wia(a, sep=' '):
	sys.stdout.write(sep.join([str(x) for x in a]))
	sys.stdout.write('\n')

def solve(n, k, ee):
	g = [[] for _ in range(n)]
	for e in ee:
		g[e[0]].append(e[1])
		g[e[1]].append(e[0])
	leafs = [[] for _ in range(n)]
	for i in range(n):
		if len(g[i]) == 1:
			leafs[g[i][0]].append(i)
	deg = [len(g[i]) for i in range(n)]
	deleted = set()
	ans = 0
	q = [i for i in range(n) if len(leafs[i]) >= k]
	while q:
		v = q.pop()
		if v in deleted:
			continue
		x = len(leafs[v]) // k
		cnt = x * k
		ans += x
		while cnt > 0:
			w = leafs[v].pop()
			deleted.add(w)
			cnt -= 1
		deg[v] -= x * k
		if deg[v] == 1:
			for w in g[v]:
				if w not in deleted:
					leafs[w].append(v)
					if len(leafs[w]) == k:
						q.append(w)
	return ans

def main():
	for _ in range(ri()):
		(n, k) = ria()
		e = []
		for i in range(n - 1):
			(xi, yi) = ria()
			xi -= 1
			yi -= 1
			e.append([xi, yi])
		wi(solve(n, k, e))
main()


import sys

def input():
	return sys.stdin.readline().rstrip()

def input_split():
	return [int(i) for i in input().split()]
testCases = int(input())
answers = []
for _ in range(testCases):
	(n, k) = input_split()
	present = [True for i in range(n)]
	edges = [set() for _ in range(n)]
	for _ in range(n - 1):
		(x, y) = input_split()
		x -= 1
		y -= 1
		edges[x].add(y)
		edges[y].add(x)
	deletions = 0
	deleted_till_now = set()
	leaves = [0 for i in range(n)]
	for i in range(n):
		for node in edges[i]:
			if len(edges[node]) == 1:
				leaves[i] += 1
	pending = []
	for i in range(n):
		if leaves[i] >= k:
			pending.append(i)
	while len(pending) != 0:
		last = pending.pop()
		num = leaves[last]
		if num < k or not present[last]:
			pass
		else:
			leaves_removed = num - num % k
			dels = num // k
			deletions += dels
			to_remove = set()
			for node in edges[last]:
				if len(edges[node]) == 1:
					to_remove.add(node)
					present[node] = False
					if len(to_remove) == leaves_removed:
						break
			edges[last] = edges[last].difference(to_remove)
			leaves[last] = num % k
			if len(edges[last]) == 1:
				parent = list(edges[last])[0]
				leaves[parent] += 1
				if leaves[parent] >= k:
					pending.append(parent)
	answers.append(deletions)
print(*answers, sep='\n')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	adj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = map(lambda s: int(s) - 1, input().split())
		adj[a].append(b)
		adj[b].append(a)
	if k == 1:
		print(n - 1)
		continue
	V = [False] * n
	C = [0] * n
	Q = []

	def is_leaf(i):
		return len(adj[i]) == 1

	def enq(i):
		if V[i] or sum((is_leaf(j) for j in adj[i])) < k:
			return
		V[i] = True
		Q.append(i)
	for (i, a) in enumerate(adj):
		if len(a) == 1:
			j = a[0]
			C[j] += 1
			if C[j] >= k and (not V[j]):
				V[j] = True
				Q.append(j)
	res = 0
	for i in Q:
		V[i] = False
		nadj = []
		leafc = []
		for j in adj[i]:
			if is_leaf(j):
				leafc.append(j)
			else:
				nadj.append(j)
		while len(leafc) >= k:
			res += 1
			for _ in range(k):
				leafc.pop()
		nadj.extend(leafc)
		adj[i] = nadj
		if is_leaf(i):
			enq(nadj[0])
	print(res)


import sys
import heapq
inpy = [int(x) for x in sys.stdin.read().split()]
t = inpy[0]
index = 1
for _ in range(t):
	(n, k) = (inpy[index], inpy[index + 1])
	index += 2
	edges = [set() for _ in range(n + 1)]
	memo = [0] * (n + 1)
	for i in range(n - 1):
		(a, b) = (inpy[index], inpy[index + 1])
		index += 2
		edges[a].add(b)
		edges[b].add(a)
	(que, no) = (set(), set())
	for i in range(1, n + 1):
		if i not in no and len(edges[i]) == 1:
			x = edges[i].pop()
			memo[x] += 1
			edges[x].remove(i)
			no.add(x)
	for i in range(1, n + 1):
		if memo[i] >= k:
			que.add(i)
	res = 0
	while que:
		x = que.pop()
		res += memo[x] // k
		memo[x] = memo[x] % k
		if len(edges[x]) == 1 and memo[x] == 0:
			y = edges[x].pop()
			memo[y] += 1
			if memo[y] >= k:
				que.add(y)
			edges[y].remove(x)
	print(res)


import collections
t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	g = collections.defaultdict(list)
	for j in range(n - 1):
		(x, y) = map(int, input().split())
		g[x].append(y)
		g[y].append(x)
	if k == 1:
		print(n - 1)
	else:
		leaf = {}
		a = set()
		b = {}
		l = {}
		for v in g:
			p = 0
			q = 0
			for u in g[v]:
				q = q + 1
				if len(g[u]) == 1:
					p = p + 1
					leaf[u] = 1
			if p >= k:
				a.add(v)
			b[v] = p
			l[v] = q
		c = 0
		while a != set():
			p = a.pop()
			te = b[p] // k
			c = c + te
			if b[p] % k == 0 and l[p] - te * k == 1:
				leaf[p] = 1
				b[p] = 0
				l[p] = 1
				for v in g[p]:
					if v not in leaf:
						b[v] = b[v] + 1
						if b[v] >= k:
							a.add(v)
						break
			else:
				b[p] = b[p] - te * k
				l[p] = l[p] - te * k
		print(c)


from sys import stdin
from collections import deque
input = stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	adj = [[] for _ in range(n)]
	frd = [set() for _ in range(n)]
	cnt = [0] * n
	is_leaf = [False] * n
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	if k == 1:
		print(n - 1)
		continue
	for i in range(n):
		if len(adj[i]) == 1:
			is_leaf[i] = True
			cnt[adj[i][0]] += 1
	q = deque()
	for u in range(n):
		if cnt[u] >= k:
			q.append(u)
		for v in adj[u]:
			if not is_leaf[v]:
				frd[u].add(v)
	ans = 0
	while len(q) > 0:
		u = q.popleft()
		ans += cnt[u] // k
		cnt[u] %= k
		if cnt[u] == 0 and len(frd[u]) == 1:
			p = frd[u].pop()
			frd[p].remove(u)
			cnt[p] += 1
			if cnt[p] >= k:
				q.append(p)
	print(ans)


def crop_set(s, n):
	new = set()
	it = iter(s)
	for i in range(n):
		new.add(next(it))
	return new

class Vertex:
	__slots__ = ('vertexes', 'leaves', 'graph')

	def __init__(self, graph):
		self.vertexes = set()
		self.leaves = 0
		self.graph = graph

	def try_to_leave(self):
		if len(self.vertexes) + self.leaves == 1:
			if self.vertexes:
				parent = self.vertexes.pop()
				parent.vertexes.remove(self)
				parent.leaves += 1
				parent.update()
				self.vertexes.add(parent)

	def update(self):
		self.graph[self] = self.leaves

class Tree:

	def __init__(self, n, k):
		self.k = k
		self.lc = [set() for _ in range(n // k + 1)]
		self.dlc = dict()
		self.max = 0

	def add_vertex(self, v):
		self.dlc[v] = 0
		self.lc[0].add(v)
		v.update()

	def __setitem__(self, key, value):
		value = value // self.k
		if self.max == self.dlc[key] > value:
			self.lc[self.max].discard(key)
			while not self.lc[self.max]:
				self.max -= 1
		else:
			self.lc[self.dlc[key]].discard(key)
		if value > self.max:
			self.max = value
		self.dlc[key] = value
		self.lc[value].add(key)

def to_int_decrement(s):
	return int(s) - 1

def solve():
	(n, k) = list(map(int, input().split()))
	tree = Tree(n, k)
	graph = [Vertex(tree) for _ in range(n)]
	for _ in range(n - 1):
		(a, b) = list(map(to_int_decrement, input().split()))
		graph[a].vertexes.add(graph[b])
		graph[b].vertexes.add(graph[a])
	if k == 1:
		print(n - 1)
		return
	for v in graph:
		tree.add_vertex(v)
	for v in graph:
		v.try_to_leave()
	c = 0
	while tree.max > 0:
		v = tree.lc[tree.max].pop()
		c += v.leaves // k
		v.leaves -= v.leaves // k * k
		v.try_to_leave()
		v.update()
	print(c)
for _ in range(int(input())):
	solve()


from bisect import *
from collections import *
from math import gcd, ceil, sqrt, floor, inf
from heapq import *
from itertools import *
from operator import add, mul, sub, xor, truediv, floordiv
from functools import *
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())
from types import GeneratorType

def bootstrap(f, stack=[]):

	def wrappedfunc(*args, **kwargs):
		if stack:
			return f(*args, **kwargs)
		else:
			to = f(*args, **kwargs)
			while True:
				if type(to) is GeneratorType:
					stack.append(to)
					to = next(to)
				else:
					stack.pop()
					if not stack:
						break
					to = stack[-1].send(to)
			return to
	return wrappedfunc
farr = [1]
ifa = []

def fact(x, mod=0):
	if mod:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr) % mod)
	else:
		while x >= len(farr):
			farr.append(farr[-1] * len(farr))
	return farr[x]

def ifact(x, mod):
	global ifa
	ifa.append(pow(farr[-1], mod - 2, mod))
	for i in range(x, 0, -1):
		ifa.append(ifa[-1] * i % mod)
	ifa = ifa[::-1]

def per(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return fact(i) // fact(i - j)
	return farr[i] * ifa[i - j] % mod

def com(i, j, mod=0):
	if i < j:
		return 0
	if not mod:
		return per(i, j) // fact(j)
	return per(i, j, mod) * ifa[j] % mod

def catalan(n):
	return com(2 * n, n) // (n + 1)

def linc(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t > f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rinc(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t < f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def ldec(f, t, l, r):
	while l < r:
		mid = (l + r) // 2
		if t < f(mid):
			l = mid + 1
		else:
			r = mid
	return l

def rdec(f, t, l, r):
	while l < r:
		mid = (l + r + 1) // 2
		if t > f(mid):
			r = mid - 1
		else:
			l = mid
	return l

def isprime(n):
	for i in range(2, int(n ** 0.5) + 1):
		if n % i == 0:
			return False
	return True

def binfun(x):
	c = 0
	for w in arr:
		c += ceil(w / x)
	return c

def lowbit(n):
	return n & -n

def inverse(a, m):
	a %= m
	if a <= 1:
		return a
	return (1 - inverse(m, a) * m) // a % m

class BIT:

	def __init__(self, arr):
		self.arr = arr
		self.n = len(arr) - 1

	def update(self, x, v):
		while x <= self.n:
			self.arr[x] += v
			x += x & -x

	def query(self, x):
		ans = 0
		while x:
			ans += self.arr[x]
			x &= x - 1
		return ans

class DSU:

	def __init__(self, n):
		self.c = [-1] * n

	def same(self, x, y):
		return self.find(x) == self.find(y)

	def find(self, x):
		if self.c[x] < 0:
			return x
		self.c[x] = self.find(self.c[x])
		return self.c[x]

	def union(self, u, v):
		(u, v) = (self.find(u), self.find(v))
		if u == v:
			return False
		if self.c[u] < self.c[v]:
			(u, v) = (v, u)
		self.c[u] += self.c[v]
		self.c[v] = u
		return True

	def size(self, x):
		return -self.c[self.find(x)]

class UFS:

	def __init__(self, n):
		self.parent = [i for i in range(n)]
		self.ranks = [0] * n

	def find(self, x):
		if x != self.parent[x]:
			self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def union(self, u, v):
		(pu, pv) = (self.find(u), self.find(v))
		if pu == pv:
			return False
		if self.ranks[pu] >= self.ranks[pv]:
			self.parent[pv] = pu
			if self.ranks[pv] == self.ranks[pu]:
				self.ranks[pu] += 1
		else:
			self.parent[pu] = pv

def Prime(n):
	c = 0
	prime = []
	flag = [0] * (n + 1)
	for i in range(2, n + 1):
		if not flag[i]:
			prime.append(i)
			c += 1
		for j in range(c):
			if i * prime[j] > n:
				break
			flag[i * prime[j]] = prime[j]
			if i % prime[j] == 0:
				break
	return prime

def dij(s, graph):
	d = {}
	d[s] = 0
	heap = [(0, s)]
	seen = set()
	while heap:
		(dis, u) = heappop(heap)
		if u in seen:
			continue
		for v in graph[u]:
			if v not in d or d[v] > d[u] + graph[u][v]:
				d[v] = d[u] + graph[u][v]
				heappush(heap, (d[v], v))
	return d

def GP(it):
	return [[ch, len(list(g))] for (ch, g) in groupby(it)]

class DLN:

	def __init__(self, val):
		self.val = val
		self.pre = None
		self.next = None

@bootstrap
def dfs(r, p):
	if len(g[r]) == 1 and p != -1:
		isl[r] = 1
		yield 1
	tmp = 0
	for ch in g[r]:
		if ch != p:
			tmp += (yield dfs(ch, r))
	cnt[r] += tmp
	if p == -1 and len(g[r]) == 1:
		isl[r] = 1
		cnt[g[r][0]] += 1
	yield 0
t = N()
for i in range(t):
	(n, k) = RL()
	g = [[] for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = RL()
		g[u].append(v)
		g[v].append(u)
	if k == 1:
		print(n - 1)
		continue
	isl = [0] * (n + 1)
	cnt = [0] * (n + 1)
	dfs(1, -1)
	q = deque()
	ans = 0
	vis = [0] * (n + 1)
	for i in range(1, n + 1):
		if cnt[i] >= k:
			q.append(i)
			vis[i] = 1
	act = cnt.copy()
	while q:
		u = q.popleft()
		ans += act[u] // k
		act[u] %= k
		vis[u] = 0
		if act[u] == 0 and len(g[u]) - cnt[u] == 1:
			for v in g[u]:
				if not isl[v]:
					cnt[v] += 1
					act[v] += 1
					isl[u] = 1
					if act[v] >= k and (not vis[v]):
						q.append(v)
						vis[v] = 1
					break
	print(ans)


from collections import defaultdict, deque
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	g = defaultdict(list)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		g[u].append(v)
		g[v].append(u)
	if k == 1:
		print(n - 1)
		continue
	indeg = [0] * n
	revdeg = [0] * n
	dq = deque()
	for i in range(n):
		indeg[i] = len(g[i])
		for j in g[i]:
			if len(g[j]) == 1:
				revdeg[i] += 1
		if revdeg[i] >= k:
			dq.appendleft(i)
	ans = 0
	while dq:
		ans += 1
		u = dq.pop()
		indeg[u] -= k
		revdeg[u] -= k
		if revdeg[u] >= k:
			dq.appendleft(u)
		elif indeg[u] == 1 and revdeg[u] == 0:
			for j in g[u]:
				revdeg[j] += 1
				if revdeg[j] == k:
					dq.appendleft(j)
	print(ans)


def main():
	from heapq import heapify, heappop, heappush
	import sys
	input = sys.stdin.readline
	for __ in [0] * int(input()):
		(N, K) = list(map(int, input().split()))
		G = [[] for _ in [0] * N]
		deg = [0] * N
		for _ in [0] * (N - 1):
			(a, b) = list(map(int, input().split()))
			a -= 1
			b -= 1
			G[a].append(b)
			G[b].append(a)
			deg[a] += 1
			deg[b] += 1
		if K == 1:
			print(N - 1)
			continue
		leaf = [0] * N
		for v in range(N):
			if deg[v] == 1:
				u = G[v][0]
				leaf[u] += 1
		L = [(-l, v) for (v, l) in enumerate(leaf) if l >= K]
		heapify(L)
		ans = 0
		while L:
			(l, v) = heappop(L)
			if -l != leaf[v]:
				continue
			(q, r) = divmod(-l, K)
			ans += q
			leaf[v] = r
			deg[v] -= K * q
			p = -1
			cnt = 0
			for u in G[v]:
				if deg[u] == 1 and cnt < K * q:
					cnt += 1
					deg[u] = 0
				elif deg[u]:
					p = u
				if cnt == K * q and (deg[v] != 1 or p != -1):
					break
			if deg[v] == 1:
				if p != -1:
					leaf[p] += 1
					if leaf[p] >= K:
						heappush(L, (-leaf[p], p))
		print(ans)

def __starting_point():
	main()
__starting_point()


from collections import defaultdict, deque
import sys
input = sys.stdin.readline
t = int(input())
for ii in range(t):
	graph = defaultdict(list)
	(n, k) = map(int, input().split())
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		graph[u].append(v)
		graph[v].append(u)
	if k == 1:
		print(n - 1)
	else:
		leaves = deque()
		for i in graph:
			if len(graph[i]) == 1:
				leaves.append(i)
		treecount = [0] * (n + 1)
		for i in leaves:
			treecount[i] = -1
		ans = 0
		while leaves:
			size = len(leaves)
			for j in range(size):
				vertex = leaves.popleft()
				treecount[vertex] = 10000000
				for i in graph[vertex]:
					if treecount[i] != -1 and treecount[i] < 10000000:
						treecount[i] += 1
						if treecount[i] % k == 0:
							ans += 1
							if treecount[i] == len(graph[i]) - 1:
								treecount[i] = -1
								leaves.append(i)
		else:
			sys.stdout.write(str(ans) + '\n')


from collections import defaultdict, deque
import heapq

class Graph:

	def __init__(self, vertices):
		self.graph = [defaultdict() for x in range(vertices + 1)]
		self.V = vertices

	def addEdge(self, u, v, w=1):
		self.graph[u][v] = w
		self.graph[v][u] = w

	def solve(self, in_degree, k):
		flag = [0] * (n + 1)
		leaves = defaultdict(int)
		for i in range(1, self.V + 1):
			if in_degree[i] == 1:
				leaves[list(self.graph[i].keys())[0]] += 1
				flag[i] = 1
		q = set()
		for p in leaves:
			if leaves[p] >= k:
				q.add(p)
		ans = 0
		while q:
			now = q.pop()
			ans += 1
			leaves[now] -= k
			if leaves[now] >= k:
				q.add(now)
			elif leaves[now] == 0:
				(conn, par) = (0, 0)
				for i in self.graph[now]:
					if flag[i] == 0:
						conn += 1
						par = i
				if conn == 1:
					flag[now] = 1
					leaves[par] += 1
					if leaves[par] == k:
						q.add(par)
		return ans
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	g = Graph(n)
	in_degree = [0] * (n + 1)
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		g.addEdge(u, v)
		in_degree[u] += 1
		in_degree[v] += 1
	if k == 1:
		print(n - 1)
	else:
		print(g.solve(in_degree, k))


t = int(input())
Maxn = 210000
while t > 0:
	t -= 1
	(n, k) = map(int, input().split())
	d = [0] * (n + 1)
	bj = [0] * (n + 1)
	flag = [0] * (n + 1)
	to = [[]]
	for i in range(0, n):
		to.append([])
	for i in range(1, n):
		(u, v) = map(int, input().split())
		to[u].append(v)
		to[v].append(u)
		d[u] += 1
		d[v] += 1
	if k == 1:
		print(n - 1)
		continue
	que = []
	for i in range(1, n + 1):
		if d[i] == 1:
			bj[to[i][0]] += 1
			flag[i] = 1
	for i in range(1, n + 1):
		if bj[i] >= k:
			que.append(i)
	ans = 0
	while len(que):
		now = que.pop()
		ans += 1
		bj[now] -= k
		if bj[now] >= k:
			que.append(now)
			continue
		if bj[now]:
			continue
		sxz = 0
		nh = 0
		for i in to[now]:
			if flag[i] == 0:
				sxz += 1
				nh = i
		if sxz == 1:
			flag[now] = 1
			bj[nh] += 1
			if bj[nh] == k:
				que.append(nh)
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	edge = [[] for i in range(n)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		edge[x - 1].append(y - 1)
		edge[y - 1].append(x - 1)
	LEAF = [[] for i in range(n)]
	V = [0] * n
	for i in range(n):
		if len(edge[i]) == 1:
			LEAF[edge[i][0]].append(i)
	Q = [i for i in range(n) if len(LEAF[i]) >= k]
	D = [len(edge[i]) for i in range(n)]
	N = edge
	ans = 0
	while Q:
		v = Q.pop()
		if V[v] == 1:
			continue
		q = len(LEAF[v]) // k
		count = q * k
		ans += q
		while count:
			dv = LEAF[v].pop()
			V[dv] = 1
			count -= 1
		D[v] -= q * k
		if D[v] == 1:
			for nv in N[v]:
				if V[nv] == 0:
					LEAF[nv].append(v)
					if len(LEAF[nv]) == k:
						Q.append(nv)
					break
	if k == 1:
		print(n - 1)
	else:
		print(ans)


from sys import stdin, stdout
import functools
import sys, os, math
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	DS = [0] * (N + 1)
	LeafNum = [0] * (N + 1)
	g = [[] for _ in range(N + 1)]
	for _ in range(N - 1):
		(u, v) = map(int, input().split())
		DS[u] += 1
		DS[v] += 1
		g[u].append(v)
		g[v].append(u)
	for u in range(1, N + 1):
		if DS[u] == 1:
			for v in g[u]:
				LeafNum[v] += 1
	if K == 1:
		print(N - 1)
		continue
	q = set()
	for u in range(1, N + 1):
		if LeafNum[u] >= K:
			q.add(u)
	ans = 0
	while len(q) > 0:
		u = q.pop()
		nl = LeafNum[u]
		ans += int(nl / K)
		LeafNum[u] = nl % K
		dn = int(nl / K) * K
		DS[u] -= int(nl / K) * K
		if DS[u] == 1:
			for v in g[u]:
				if DS[v] == 1 and dn > 0:
					dn -= 1
					continue
				LeafNum[v] += 1
				if LeafNum[v] >= K and v not in q:
					q.add(v)
	print(ans)


import sys
input = sys.stdin.readline
f = lambda : map(int, input().split())
for _ in range(int(input())):
	(n, k) = f()
	g = [[] for i in range(n + 1)]
	deg = [0] * (n + 1)
	isLeaf = [0] * (n + 1)
	numLeaves = [0] * (n + 1)
	q = []
	ans = 0
	for __ in range(n - 1):
		(a, b) = f()
		g[a].append(b)
		g[b].append(a)
		deg[a] += 1
		deg[b] += 1
	if k == 1:
		print(n - 1)
		continue
	for i in range(1, n + 1):
		if deg[i] == 1:
			isLeaf[i] = True
			numLeaves[g[i][0]] += 1
	for i in range(1, n + 1):
		if numLeaves[i] >= k:
			q.append(i)
	while len(q):
		u = q.pop()
		ans += 1
		numLeaves[u] -= k
		if numLeaves[u]:
			if numLeaves[u] >= k:
				q.append(u)
			continue
		(numP, v) = (0, 0)
		for i in g[u]:
			if not isLeaf[i]:
				numP += 1
				v = i
		if numP == 1:
			numLeaves[v] += 1
			isLeaf[u] = True
			if numLeaves[v] == k:
				q.append(v)
	print(ans)


from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush, heappop, heapify
import math
from collections import *
from functools import reduce, cmp_to_key
import sys
input = sys.stdin.readline
M = mod = 998244353

def factors(n):
	return sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))

def inv_mod(n):
	return pow(n, mod - 2, mod)

def li():
	return [int(i) for i in input().rstrip('\n').split()]

def st():
	return input().rstrip('\n')

def val():
	return int(input().rstrip('\n'))

def li2():
	return [i for i in input().rstrip('\n')]

def li3():
	return [int(i) for i in input().rstrip('\n')]
for _ in range(val()):
	(n, k) = li()
	d = defaultdict(set)
	for i in range(n - 1):
		(a, b) = li()
		d[a].add(b)
		d[b].add(a)
	thistime = 1
	he = deque()
	visited = {}
	for i in d:
		if len(d[i]) == 1:
			visited[i] = 1
			he.append(i)
	ans = 0
	counts = defaultdict(int)
	while he:
		i = he.popleft()
		for j in list(d[i]):
			counts[j] += 1
			d[i].remove(j)
			d[j].remove(i)
			if counts[j] == k:
				thistime = 1
				ans += 1
				counts[j] = 0
				if len(d[j]) == 1:
					if j not in visited:
						he.append(j)
					visited[j] = 1
	print(ans)


for i in range(int(input())):
	(n, k) = list(map(int, input().split()))
	a = [[] for i in range(n)]
	b = [0] * n
	c = [0] * n
	d = [0] * n
	e = []
	for i in range(n - 1):
		(u, v) = list(map(int, input().split()))
		a[u - 1].append(v)
		a[v - 1].append(u)
		b[u - 1] += 1
		b[v - 1] += 1
	if k == 1:
		print(n - 1)
	else:
		for i in range(n):
			if b[i] == 1:
				d[i] = 1
				for j in a[i]:
					c[j - 1] += 1
		z = 0
		f = 0
		for i in range(n):
			if c[i] >= k:
				e.append(i + 1)
				f += 1
		i = 0
		while i < f:
			z += c[e[i] - 1] // k
			y = c[e[i] - 1] // k * k
			for j in a[e[i] - 1]:
				if b[j - 1] == 1:
					if y == 0:
						break
					y -= 1
					d[j - 1] = 2
					c[e[i] - 1] -= 1
					b[e[i] - 1] -= 1
			if b[e[i] - 1] == 1:
				d[e[i] - 1] = 1
				for j in a[e[i] - 1]:
					if d[j - 1] != 2:
						c[j - 1] += 1
						if c[j - 1] == k:
							e.append(j)
							f += 1
			i += 1
		print(z)


from sys import stdin
input = lambda : stdin.readline().strip()
from math import ceil, sqrt, factorial, gcd, log
from collections import deque
from bisect import bisect_left, bisect_right
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	z = [0 for i in range(n + 1)]
	graph = {i: set() for i in range(1, n + 1)}
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		graph[a].add(b)
		graph[b].add(a)
	count = 0
	if k == 1:
		count = n - 1
	else:
		freind = [set() for i in range(n + 1)]
		leaf = [False] * (n + 1)
		for i in graph:
			if len(graph[i]) == 1:
				leaf[i] = True
				for j in graph[i]:
					z[j] += 1
					break
		stack = []
		for i in range(1, n + 1):
			if z[i] >= k:
				stack.append(i)
			for j in graph[i]:
				if not leaf[j]:
					freind[i].add(j)
		while stack:
			x = stack.pop()
			count += z[x] // k
			z[x] = z[x] % k
			if z[x] == 0 and len(freind[x]) == 1:
				a = freind[x].pop()
				freind[a].remove(x)
				z[a] += 1
				if z[a] >= k:
					stack.append(a)
	print(count)


from sys import stdin

def inp():
	return stdin.buffer.readline().rstrip().decode('utf8')

def itg():
	return int(stdin.buffer.readline())

def mpint():
	return map(int, stdin.buffer.readline().split())

class SegmentTreeIndex:

	def __init__(self, data, default=0, func=max):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.real_data = data
		self.data = [-1] * (2 * _size)
		self.data[_size:_size + self._len] = range(self._len)
		for i in reversed(range(_size)):
			self.data[i] = self._index_cmp(self.data[i * 2], self.data[i * 2 + 1])

	def _index_cmp(self, idx1, idx2):
		if idx2 == -1:
			return idx1
		if idx1 == -1:
			return idx2
		if self._func(self[idx1], self[idx2]) == self[idx1]:
			return idx1
		return idx2

	def query(self, start, stop):
		start += self._size
		stop += self._size
		res_left = res_right = -1
		while start < stop:
			if start & 1:
				res_left = self._index_cmp(res_left, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res_right = self._index_cmp(self.data[stop], res_right)
			start >>= 1
			stop >>= 1
		return self._index_cmp(res_left, res_right)

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.real_data[idx]

	def __setitem__(self, idx, value):
		self.real_data[idx] = value
		idx = idx + self._size >> 1
		while idx:
			self.data[idx] = self._index_cmp(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def __repr__(self):
		return 'SegmentTreeIndex({0})'.format(self.real_data)
from copy import deepcopy
for case in range(1, itg() + 1):
	(n, k) = mpint()
	graph = [set() for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = mpint()
		u -= 1
		v -= 1
		graph[u].add(v)
		graph[v].add(u)
	if k == 1:
		print(n - 1)
		continue
	new_graph = deepcopy(graph)
	tree = SegmentTreeIndex([0] * n)
	for i in range(n):
		if len(graph[i]) == 1:
			ancestor = next(iter(graph[i]))
			tree[ancestor] = tree[ancestor] + 1
			new_graph[ancestor].remove(i)
	ans = 0
	while True:
		idx = tree.query(0, n)
		if tree[idx] < k:
			break
		ans += 1
		tree[idx] = tree[idx] - k
		if tree[idx] == 0:
			if len(new_graph[idx]) == 1:
				ancestor = new_graph[idx].pop()
				new_graph[ancestor].remove(idx)
				tree[ancestor] = tree[ancestor] + 1
			elif len(new_graph[idx]) >= 2:
				pass
	print(ans)


from collections import deque, defaultdict
it = lambda : list(map(int, input().strip().split()))

def solve():
	(n, k) = it()
	edges = defaultdict(set)
	vis = set()
	queue = deque()
	count = [[] for _ in range(n + 1)]
	for _ in range(n - 1):
		(x, y) = it()
		edges[x].add(y)
		edges[y].add(x)
	if k == 1:
		return n - 1
	for x in range(1, n + 1):
		if len(edges[x]) == 1:
			vis.add(x)
			queue.append(x)
	ans = 0
	while queue:
		x = queue.popleft()
		if edges[x]:
			for y in edges[x]:
				count[y].append(x)
				if len(count[y]) == k:
					ans += 1
					while count[y]:
						edges[y].discard(count[y].pop())
				if len(edges[y]) == 1 and (not y in vis):
					vis.add(y)
					queue.append(y)
	return ans
T = int(input())
ans = []
for _ in range(T):
	ans.append(solve())
for a in ans:
	print(a)


import os
import sys
from io import BytesIO, IOBase

class HeapNode:

	def __init__(self, key, count):
		self.key = key
		self.count = count

def heapKey(a, b):
	return a.count > b.count
setattr(HeapNode, '__lt__', lambda self, other: heapKey(self, other))

class Heap:

	def __init__(self):
		self.heap = list()
		self.mapping = dict()

	def pop(self):
		if len(self.heap) == 0:
			return None
		lastelt = self.heap.pop()
		if self.heap:
			returnitem = self.heap[0]
			self.heap[0] = lastelt
			self.mapping[lastelt.key] = 0
			self._siftup(0)
			self.mapping.pop(returnitem.key)
			return returnitem
		self.mapping.pop(lastelt.key)
		return lastelt

	def _siftup(self, pos):
		endpos = len(self.heap)
		startpos = pos
		newitem = self.heap[pos]
		childpos = 2 * pos + 1
		while childpos < endpos:
			rightpos = childpos + 1
			if rightpos < endpos and (not self.heap[childpos] < self.heap[rightpos]):
				childpos = rightpos
			self.heap[pos] = self.heap[childpos]
			self.mapping[self.heap[pos].key] = pos
			pos = childpos
			childpos = 2 * pos + 1
		self.heap[pos] = newitem
		self.mapping[self.heap[pos].key] = pos
		self._siftdown(startpos, pos)

	def _siftdown(self, startpos, pos):
		newitem = self.heap[pos]
		while pos > startpos:
			parentpos = pos - 1 >> 1
			parent = self.heap[parentpos]
			if newitem < parent:
				self.heap[pos] = parent
				self.mapping[parent.key] = pos
				pos = parentpos
				continue
			break
		self.heap[pos] = newitem
		self.mapping[newitem.key] = pos

	def push(self, item):
		self.heap.append(item)
		self.mapping[item.key] = len(self.heap) - 1
		self._siftdown(0, len(self.heap) - 1)

	def remove(self, key):
		pos = self.mapping[key]
		self.heap[pos].count = -1
		self._siftup(pos)

	def increment(self, key):
		pos = self.mapping[key]
		self.heap[pos].count += 1
		self._siftdown(0, pos)

def main():
	t = int(input())
	for _ in range(t):
		(n, k) = map(int, input().split())
		G = dict()
		for _ in range(n - 1):
			(u, v) = map(int, input().split())
			if u not in G:
				G.setdefault(u, set())
			if v not in G:
				G.setdefault(v, set())
			G[u].add(v)
			G[v].add(u)
		heap = Heap()
		for i in range(1, n + 1):
			count = 0
			for v in G[i]:
				if len(G[v]) == 1:
					count += 1
			heap.push(HeapNode(i, count))
		ans = 0
		while heap.heap[0].count >= k:
			popped = heap.pop()
			node = popped.key
			initCount = popped.count
			leaves = list()
			leafCount = 0
			for v in G[node]:
				if len(G[v]) == 1:
					leafCount += 1
			size = leafCount // k * k
			for v in G[node]:
				if len(leaves) >= size:
					break
				if len(G[v]) == 1:
					leaves.append(v)
			for v in leaves:
				heap.remove(v)
				G[node].discard(v)
				G.pop(v)
			if len(G[node]) == 1:
				for v in G[node]:
					heap.increment(v)
			heap.push(HeapNode(node, initCount - size))
			ans += leafCount // k
		print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = lambda s: self.buffer.write(s.encode()) if self.writable else None

	def read(self):
		if self.buffer.tell():
			return self.buffer.read().decode('ascii')
		return os.read(self._fd, os.fstat(self._fd).st_size).decode('ascii')

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline().decode('ascii')

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

def print(*args, sep=' ', end='\n', file=sys.stdout, flush=False):
	at_start = True
	for x in args:
		if not at_start:
			file.write(sep)
		file.write(str(x))
		at_start = False
	file.write(end)
	if flush:
		file.flush()
(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
sys.setrecursionlimit(10000)
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def RL():
	return map(int, sys.stdin.readline().rstrip().split())

def RLL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def N():
	return int(input())

def comb(n, m):
	return factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0

def perm(n, m):
	return factorial(n) // factorial(n - m) if n >= m else 0

def mdis(x1, y1, x2, y2):
	return abs(x1 - x2) + abs(y1 - y2)
mod = 998244353
INF = float('inf')
from math import factorial
from collections import Counter, defaultdict, deque
from heapq import heapify, heappop, heappush

def main():
	for _ in range(N()):
		(n, k) = RL()
		gp = [[] for _ in range(n + 1)]
		ind = [0] * (n + 1)
		for _ in range(n - 1):
			(a, b) = RL()
			gp[a].append(b)
			gp[b].append(a)
			ind[a] += 1
			ind[b] += 1
		if k == 1:
			print(n - 1)
			continue
		q = []
		vis = [0] * (n + 1)
		for i in range(1, n + 1):
			if ind[i] == 1:
				q.append(i)
				vis[i] = 1
		num = [0] * (n + 1)
		res = 0
		while q:
			nd = q.pop()
			ind[nd] -= 1
			for nex in gp[nd]:
				if vis[nex] == 1:
					continue
				ind[nex] -= 1
				num[nex] += 1
				if num[nex] % k == 0:
					res += 1
					if ind[nex] == 1:
						q.append(nex)
						vis[nex] = 1
		print(res)
main()


from collections import deque
for t in range(int(input())):
	(n, k) = map(int, input().split())
	tree = [[] for i in range(n)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		tree[x - 1].append(y - 1)
		tree[y - 1].append(x - 1)
	numLeaves = [0 for i in range(n)]
	isLeaf = [False for i in range(n)]
	for i in range(n):
		if len(tree[i]) == 1:
			numLeaves[tree[i][0]] += 1
			isLeaf[i] = True
	if k == 1:
		print(n - 1)
		continue
	q = []
	for i in range(n):
		if numLeaves[i] >= k:
			q.append(i)
	q = deque(q)
	ans = 0
	while len(q) > 0:
		curr = q.popleft()
		ans += numLeaves[curr] // k
		if numLeaves[curr] % k == 0:
			numLeaves[curr] = 0
			cnt = 0
			nonLeafNeib = -1
			for neib in tree[curr]:
				if not isLeaf[neib]:
					cnt += 1
					nonLeafNeib = neib
					if cnt == 2:
						break
			if cnt == 1:
				isLeaf[curr] = True
				numLeaves[nonLeafNeib] += 1
				if numLeaves[nonLeafNeib] == k:
					q.append(nonLeafNeib)
		else:
			numLeaves[curr] = numLeaves[curr] % k
	print(ans)


import sys
input = sys.stdin.readline

def read_list():
	return map(int, input().split())

def print_list(l):
	print(' '.join(map(str, l)))
from collections import defaultdict
N = int(input())
for _ in range(N):
	(n, k) = read_list()
	if k == 1:
		for _ in range(n - 1):
			input()
		print(n - 1)
	else:
		dic = defaultdict(int)
		de = defaultdict(set)
		for _ in range(n - 1):
			(a, b) = read_list()
			de[a].add(b)
			de[b].add(a)
		for i in range(1, n + 1):
			dic[i] = len(de[i])
		dd = defaultdict(int)
		for v in range(1, n + 1):
			if dic[v] >= k:
				for u in de[v]:
					if dic[u] == 1:
						dd[v] += 1
		s = set((i for i in range(1, n + 1) if dd[i] >= k))
		res = 0
		while s:
			v = s.pop()
			while dd[v] >= k:
				res += 1
				dic[v] -= k
				dd[v] -= k
				if dic[v] == 1:
					for t in de[v]:
						if dic[t] >= k:
							dd[t] += 1
							if dd[t] >= k:
								s.add(t)
		print(res)


import sys
import math
from _collections import deque
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
ma = int(10000000000000000)
mod = 1000000007
tc = int(input())
for p in range(tc):
	(n, k) = map(int, input().split())
	adj = [[] for i in range(n + 2)]
	deg = [0] * (n + 2)
	b = [0] * (n + 2)
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		deg[u] += 1
		deg[v] += 1
		adj[u].append(v)
		adj[v].append(u)
	if k == 1:
		print(n - 1)
		continue
	for i in range(1, n + 1):
		if deg[i] == 1:
			x = adj[i][0]
			b[x] += 1
	q = []
	for i in range(1, n + 1):
		if b[i] >= k:
			q.append(i)
	ans = int(0)
	while len(q) > 0:
		u = int(q[0])
		q.pop(0)
		cn = int(b[u] / k)
		ans += cn
		deg[u] = deg[u] - cn * k
		b[u] %= k
		if deg[u] == 1:
			par = int(-1)
			for j in adj[u]:
				if deg[j] > 1:
					par = j
			if par == -1:
				continue
			b[par] += 1
			if b[par] == k:
				q.append(par)
	print(ans)


from sys import stdin
input = stdin.readline

def solve():
	(n, k) = map(int, input().split())
	adj = [[] for _ in range(n)]
	frd = [set() for _ in range(n)]
	cnt = [0] * n
	is_leaf = [False] * n
	for _ in range(n - 1):
		(u, v) = map(int, input().split())
		u -= 1
		v -= 1
		adj[u].append(v)
		adj[v].append(u)
	if k == 1:
		print(n - 1)
		return
	for i in range(n):
		if len(adj[i]) == 1:
			is_leaf[i] = True
			cnt[adj[i][0]] += 1
	q = []
	for u in range(n):
		if cnt[u] >= k:
			q.append(u)
		for v in adj[u]:
			if not is_leaf[v]:
				frd[u].add(v)
	ans = 0
	while len(q) > 0:
		u = q.pop()
		ans += cnt[u] // k
		cnt[u] %= k
		if cnt[u] == 0 and len(frd[u]) == 1:
			p = frd[u].pop()
			frd[p].remove(u)
			cnt[p] += 1
			if cnt[p] >= k:
				q.append(p)
	print(ans)

def main():
	t = int(input())
	for _ in range(t):
		solve()
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	edge = [[] for i in range(n)]
	for i in range(n - 1):
		(x, y) = map(int, input().split())
		edge[x - 1].append(y - 1)
		edge[y - 1].append(x - 1)
	leaf = [[] for i in range(n)]
	for i in range(n):
		if len(edge[i]) == 1:
			leaf[edge[i][0]].append(i)
	que = [i for i in range(n) if len(leaf[i]) >= k]
	deg = [len(edge[i]) for i in range(n)]
	delete = set([])
	ans = 0
	while que:
		v = que.pop()
		if v in delete:
			continue
		q = len(leaf[v]) // k
		count = q * k
		ans += q
		while count:
			dv = leaf[v].pop()
			delete.add(dv)
			count -= 1
		deg[v] -= q * k
		if deg[v] == 1:
			for nv in edge[v]:
				if nv not in delete:
					leaf[nv].append(v)
					if len(leaf[nv]) == k:
						que.append(nv)
					break
	print(ans)


import sys
sys.setrecursionlimit(10 ** 5)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def MI1():
	return map(int1, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]
for _ in range(II()):
	(n, k) = MI()
	to = [[] for _ in range(n)]
	for _ in range(n - 1):
		(u, v) = MI1()
		to[u].append(v)
		to[v].append(u)
	if k == 1:
		print(n - 1)
		continue
	dp = [0] * n
	beleaf = [False] * n
	leaves = [0] * n
	stack = [(0, -1)]
	first = [True] * n
	while stack:
		(u, pu) = stack.pop()
		if first[u]:
			first[u] = False
			stack.append((u, pu))
			for v in to[u]:
				if v == pu:
					continue
				stack.append((v, u))
		else:
			dp[u] = leaves[u] // k
			if pu != -1 and dp[u] * k + 1 == len(to[u]):
				leaves[pu] += 1
				beleaf[u] = True
			for v in to[u]:
				if v == pu:
					continue
				dp[u] += dp[v]
	stack = [(0, -1)]
	while stack:
		(u, pu) = stack.pop()
		for v in to[u]:
			if v == pu:
				continue
			dp[v] = dp[u]
			if (leaves[u] - beleaf[v]) % k == 0 and leaves[u] - beleaf[v] + 1 == len(to[u]):
				leaves[v] += 1
				if leaves[v] % k == 0:
					dp[v] += 1
			stack.append((v, u))
	print(max(dp))


import io
import os
from collections import Counter, defaultdict, deque

def solve(N, K, edges):
	if K == 1:
		return len(edges)
	graph = [[] for i in range(N)]
	for (u, v) in edges:
		graph[u].append(v)
		graph[v].append(u)
	q = set()
	leaves = set()
	for u in range(N):
		if len(graph[u]) == 1:
			(v,) = graph[u]
			q.add(v)
			leaves.add(u)
	removed = set()
	q = deque(q)
	while q:
		parent = q.popleft()
		if parent in removed or parent in leaves:
			continue
		children = [v for v in graph[parent] if v in leaves and v not in removed]
		for i in range(len(children) // K * K):
			removed.add(children[i])
		if len(children) % K == 0:
			nbrs = [v for v in graph[parent] if v not in removed]
			if len(nbrs) == 1:
				leaves.add(parent)
				q.append(nbrs[0])
	return len(removed) // K
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
T = int(input())
for t in range(T):
	(N, K) = [int(x) for x in input().split()]
	edges = [[int(x) - 1 for x in input().split()] for i in range(N - 1)]
	ans = solve(N, K, edges)
	print(ans)


from sys import stdin, stdout
from collections import deque
t = int(stdin.readline())
for x in range(t):
	(n, k) = map(int, stdin.readline().split())
	dic = {}
	for i in range(n - 1):
		(x, y) = map(int, stdin.readline().split())
		x -= 1
		y -= 1
		if x not in dic:
			dic[x] = set()
		if y not in dic:
			dic[y] = set()
		dic[x].add(y)
		dic[y].add(x)
	if k == 1:
		print(n - 1)
		continue
	isleaf = set()
	leaves = [0 for _ in range(n)]
	for i in range(n):
		if len(dic[i]) == 1:
			isleaf.add(i)
			p = next(iter(dic[i]))
			leaves[p] += 1
	q = deque()
	frd = [set() for _ in range(n)]
	for l in range(n):
		if leaves[l] >= k:
			q.append(l)
		for v in dic[l]:
			if v not in isleaf:
				frd[l].add(v)
	ans = 0
	while len(q) > 0:
		u = q.popleft()
		ans += leaves[u] // k
		leaves[u] %= k
		if leaves[u] == 0 and len(frd[u]) == 1:
			p = frd[u].pop()
			frd[p].remove(u)
			leaves[p] += 1
			if leaves[p] >= k:
				q.append(p)
	print(ans)