You are given a tree with $N$ nodes, which are numbered from $1$ to $N$. It is rooted at Node $1$. We define a single $operation$ as follows :- 
Put a chip on the root.
Within an operation, you can "move" as many times as you like.
A move is defined as picking a node which has a chip on it and then removing the chip from that node and placing a chip on all of its children. 

A node is covered if it has at least $1$ chip placed on it.
You can do at most $K$ operations. What is the maximum number of covered nodes that you can obtain?  

Note that there is no constraint on the amount of chips placed on any node.

------ Input: ------

The input contains a single integer, $T$, which denotes the number of testcases.
The first line of each testcase will contain two integers, $N$ and $K$, denoting the number of nodes and operations allowed, respectively.
The next $N-1$ lines contain two integers $u$ and $v$ indicating that there is an edge between nodes $u$ and $v$ in the tree.

------ Output: ------
The output should consist of $T$ integers printed on separate lines. The integer on the i-th line should be the maximum number of nodes which can be covered in that testcase.

------ Constraints  ------
$1 ≤ T ≤ 5$
$2 ≤ N ≤ 5*10^{5}$
$1 ≤ K ≤ N$
Sum of $N$ over all testcases $ ≤ 5*10^{5}$
$1 ≤ u,v ≤ N$
The given graph is a tree

------ Subtasks ------
30 points : Sum of $N$ of over all testcases $ ≤ 5000 $
70 points : Original Constraints. 

----- Sample Input 1 ------ 
1
7 2
1 2
1 3
2 4
2 5
3 6
3 7
----- Sample Output 1 ------ 
6
----- explanation 1 ------ 
You can cover nodes 4,5,6,7 in the first operation and 2,3 in the second. 
2,3 for example can be covered by placing the chip on the root and then moving it to its children.

Difficulty: HARD
Tags: Geometry

Sweep line algorithms

Mathematics

Starter code:

Solutions:
from collections import deque
from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)
for _ in range(int(input())):
	(N, K) = list(map(int, input().split()))
	childnodes = defaultdict(lambda : [])
	for i in range(N - 1):
		(u, v) = list(map(int, input().split()))
		childnodes[u - 1].append(v - 1)
		childnodes[v - 1].append(u - 1)
	arr = [0] * N

	def dfs(node, arr, prev, childnodes):
		if node not in childnodes:
			arr[node] = 1
			return 1
		mx = 0
		for i in childnodes[node]:
			if i != prev:
				mx = max(dfs(i, arr, node, childnodes), mx)
		arr[node] = mx + 1
		return mx + 1
	try:
		dfs(0, arr, 0, childnodes)
	except:
		pass
	ans = [0] * (N + 1)
	for i in range(N):
		try:
			ans[arr[i]] += 1
		except:
			pass
	for i in range(1, len(ans)):
		ans[i] = ans[i] + ans[i - 1]
	print(ans[K])


from sys import stdin, setrecursionlimit
input = stdin.readline
setrecursionlimit(2 * 10 ** 5)
from collections import deque

def dfs(p, prev):
	parent[p] = prev
	for i in child[p]:
		if i == prev:
			continue
		deg[p] += 1
		dfs(i, p)

def answer():
	q = deque([])
	for p in range(1, n + 1):
		if deg[p] == 0:
			q.append([p, 1])
	ans = 0
	while len(q):
		(p, count) = q.popleft()
		ans += 1
		if count == k:
			continue
		if parent[p] == -1:
			continue
		deg[parent[p]] -= 1
		if deg[parent[p]]:
			continue
		q.append([parent[p], count + 1])
	return ans
for T in range(int(input())):
	(n, k) = map(int, input().split())
	child = [[] for i in range(n + 1)]
	deg = [0 for i in range(n + 1)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		child[u].append(v)
		child[v].append(u)
	parent = [-1 for i in range(n + 1)]
	dfs(1, -1)
	print(answer())


def ii():
	a = int(input())
	return a

def ai():
	a = list(map(int, input().split()))
	return a

def mi():
	a = map(int, input().split())
	return a
import sys
sys.setrecursionlimit(10 ** 7)

def dfs(u):
	visited[u] = True
	m = 0
	for i in range(len(g[u])):
		v = g[u][i]
		if visited[v] == False:
			depth[v] = dfs(v)
			m = max(m, depth[v])
	return m + 1
for t in range(int(input())):
	(n, k) = map(int, input().split())
	g = [[] for i in range(n)]
	for i in range(n - 1):
		(u, v) = map(int, input().split())
		g[u - 1].append(v - 1)
		g[v - 1].append(u - 1)
	depth = [0 for i in range(n)]
	visited = [False for i in range(n)]
	depth[0] = dfs(0)
	c = 0
	for i in range(n):
		if depth[i] <= k:
			c += 1
	print(c)


import sys
sys.setrecursionlimit(1000000)
t = int(input())
while t:
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	adj = []
	for _ in range(n):
		adj.append([])
	dp = [0] * n

	def dfs(u, par):
		for v in adj[u]:
			if v == par:
				continue
			dfs(v, u)
			dp[u] = max(dp[u], dp[v])
		dp[u] += 1
	for _ in range(n - 1):
		(a, b) = input().split()
		a = int(a)
		b = int(b)
		a -= 1
		b -= 1
		adj[a].append(b)
		adj[b].append(a)
	dfs(0, 0)
	ans = 0
	for i in dp:
		ans += i <= k
	print(ans)
	t -= 1


import sys
sys.setrecursionlimit(1000000)
from collections import defaultdict

def dfs(root, d, levels):
	t = 0
	for j in d[root]:
		t = max(t, dfs(j, d, levels))
	levels[t] += 1
	return t + 1
for _ in range(int(input())):
	(n, k) = [int(i) for i in input().split(' ')]
	(d, levels, visited) = (defaultdict(list), defaultdict(int), {})
	visited[1] = 1
	for i in range(n - 1):
		(u, v) = [int(i) for i in input().split(' ')]
		if u not in visited:
			(u, v) = (v, u)
		d[u].append(v)
		visited[v] = 1
	lev = dfs(1, d, levels)
	print(sum([levels[i] for i in range(min(k, lev))]))


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(n):
	bool[n] = True
	for i in hash[n]:
		if bool[i] == False:
			height[n] = max(dfs(i), height[n])
	return height[n] + 1
t = int(input())
from collections import defaultdict, Counter
for _ in range(t):
	(n, k) = map(int, input().split())
	hash = defaultdict(list)
	bool = [False] * (n + 1)
	height = [0] * (n + 1)
	for i in range(n - 1):
		(a, b) = map(int, input().split())
		hash[a].append(b)
		hash[b].append(a)
	dfs(1)
	z = Counter(height[1:])
	ka = sorted(z.values())
	ka.reverse()
	print(sum(ka[:k]))


from sys import stdin, stdout
import heapq
import cProfile, math
from collections import Counter, defaultdict, deque
from bisect import bisect_left, bisect, bisect_right
import itertools
from copy import deepcopy
from fractions import Fraction
import sys, threading
import operator as op
from functools import reduce
import sys
sys.setrecursionlimit(10 ** 6)
threading.stack_size(2 ** 27)
fac_warm_up = False
printHeap = str()
memory_constrained = False
P = 10 ** 9 + 7

class MergeFind:

	def __init__(self, n):
		self.parent = list(range(n))
		self.size = [1] * n
		self.num_sets = n
		self.lista = [[_] for _ in range(n)]

	def find(self, a):
		to_update = []
		while a != self.parent[a]:
			to_update.append(a)
			a = self.parent[a]
		for b in to_update:
			self.parent[b] = a
		return self.parent[a]

	def merge(self, a, b):
		a = self.find(a)
		b = self.find(b)
		if a == b:
			return
		if self.size[a] < self.size[b]:
			(a, b) = (b, a)
		self.num_sets -= 1
		self.parent[b] = a
		self.size[a] += self.size[b]
		self.lista[a] += self.lista[b]

	def set_size(self, a):
		return self.size[self.find(a)]

	def __len__(self):
		return self.num_sets

def display(string_to_print):
	stdout.write(str(string_to_print) + '\n')

def prime_factors(n):
	factors = dict()
	for i in range(2, math.ceil(math.sqrt(n)) + 1):
		while n % i == 0:
			if i in factors:
				factors[i] += 1
			else:
				factors[i] = 1
			n = n // i
	if n > 2:
		factors[n] = 1
	return factors

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

def fibonacci_modP(n, MOD):
	if n < 2:
		return 1
	return (cached_fn(fibonacci_modP, (n + 1) // 2, MOD) * cached_fn(fibonacci_modP, n // 2, MOD) + cached_fn(fibonacci_modP, (n - 1) // 2, MOD) * cached_fn(fibonacci_modP, (n - 2) // 2, MOD)) % MOD

def factorial_modP_Wilson(n, p):
	if p <= n:
		return 0
	res = p - 1
	for i in range(n + 1, p):
		res = res * cached_fn(InverseEuler, i, p) % p
	return res

def binary(n, digits=20):
	b = bin(n)[2:]
	b = '0' * (digits - len(b)) + b
	return b

def is_prime(n):
	if n < 4:
		return True
	if n % 2 == 0:
		return False
	if n % 3 == 0:
		return False
	i = 5
	w = 2
	while i * i <= n:
		if n % i == 0:
			return False
		i += w
		w = 6 - w
	return True

def generate_primes(n):
	prime = [True for i in range(n + 1)]
	p = 2
	while p * p <= n:
		if prime[p]:
			for i in range(p * 2, n + 1, p):
				prime[i] = False
		p += 1
	return prime
factorial_modP = []

def warm_up_fac(MOD):
	global factorial_modP, fac_warm_up
	if fac_warm_up:
		return
	factorial_modP = [1 for _ in range(fac_warm_up_size + 1)]
	for i in range(2, fac_warm_up_size):
		factorial_modP[i] = factorial_modP[i - 1] * i % MOD
	fac_warm_up = True

def InverseEuler(n, MOD):
	return pow(n, MOD - 2, MOD)

def nCr(n, r, MOD):
	global fac_warm_up, factorial_modP
	if not fac_warm_up:
		warm_up_fac(MOD)
		fac_warm_up = True
	return factorial_modP[n] * (pow(factorial_modP[r], MOD - 2, MOD) * pow(factorial_modP[n - r], MOD - 2, MOD) % MOD) % MOD

def get_int():
	return int(stdin.readline().strip())

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

def get_list():
	return list(map(int, stdin.readline().split()))
memory = dict()

def clear_cache():
	global memory
	memory = dict()

def cached_fn(fn, *args):
	global memory
	if args in memory:
		return memory[args]
	else:
		result = fn(*args)
		memory[args] = result
		return result

def ncr(n, r):
	return math.factorial(n) / (math.factorial(n - r) * math.factorial(r))

def binary_search(i, li):
	fn = lambda x: li[x] - x // i
	x = -1
	b = len(li)
	while b >= 1:
		while b + x < len(li) and fn(b + x) > 0:
			x += b
		b = b // 2
	return x
TestCases = True
optimise_for_recursion = True

def dfs(root):
	global rev_height, visited, adj
	visited[root] = True
	rev_height[root] = 0
	for i in adj[root]:
		if not visited[i]:
			rev_height[root] = max(dfs(i), rev_height[root])
	return rev_height[root] + 1

def main():
	global rev_height, visited, adj
	(n, k) = get_tuple()
	adj = [[] for _ in range(n)]
	for _ in range(n - 1):
		(x, y) = get_tuple()
		adj[x - 1].append(y - 1)
		adj[y - 1].append(x - 1)
	visited = [False for _ in range(n)]
	rev_height = [0 for _ in range(n)]
	dfs(0)
	cnt = Counter(rev_height)
	cnt = list(sorted(cnt.values(), reverse=True))
	print(sum(cnt[:k]))
if TestCases:
	for i in range(get_int()):
		main()
else:
	main() if not optimise_for_recursion else threading.Thread(target=main).start()


import sys
sys.setrecursionlimit(10 ** 9)

def dfs(no, par=-1, l=1):
	st = False
	ma = 0
	for i in adj[no]:
		if i != par:
			st = True
			a = dfs(i, no, l + 1)
			ma = max(ma, a + 1)
	if st == False:
		return 0
	lev[no] = ma
	return lev[no]
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	adj = [set() for i in range(n)]
	for __ in range(n - 1):
		(a, b) = map(int, input().split())
		adj[a - 1].add(b - 1)
		adj[b - 1].add(a - 1)
	vis = [0] * n
	vis[0] = 1
	lev = [0 for i in range(n)]
	dp = [0] * n
	dfs(0)
	ss = {}
	for i in lev:
		try:
			ss[i] += 1
		except:
			ss[i] = 1
	tt = [i for i in ss]
	tt.sort(reverse=False)
	ind = 0
	tot = 0
	co = 0
	while co < k and ind < len(tt):
		tot += ss[tt[ind]]
		ind += 1
		co += 1
	print(tot)