# Minimum Subtree Cover SUBTRCOV SOLUTION

## Minimum Subtree Cover SUBTRCOV

You are given a tree with n vertices (numbered 1,2,…,n) and an integer k.

A subtree is defined as a connected subgraph of the tree. That is, a subtree is another tree that can be obtained by removing some (possibly none) vertices and all edges incident to those vertices from T.

A subset S of vertices is called good if every subtree containing all the nodes in S has at least k nodes.

Find the size of the smallest good subset.

Input
The first line contains a single integer T, the number of test cases. The descriptions of test cases follow.
The first line of each testcase contains two integers, n and k.
The next n−1 lines each contains two integers u, v, denoting an edge between vertices u and v of the tree.
Output
For each test case print in a single line, the minimum size of a good subset.
Constraints
1≤n≤105
1≤k≤n
1≤u,v≤n
The given edges for each test case form a tree.
The sum of n over all test cases is at most 106.
Subtask #2 (70 points): original constraints

Sample Input
2
7 5
1 2
2 3
3 4
3 5
5 6
3 7
6 4
1 2
1 3
1 4
1 5
1 6
Sample Output
2
3
Explanation
Test Case 1: Consider the set S={1,6}.

The smallest subtree that contains both of the vertices in S is the path between them (1→2→3→5→6) which contains 5 vertices. Hence for k=5, the answer is 2.

Test Case 2: Consider the set S={2,3,4}.

The smallest subtree that contains these three vertices includes 4 nodes {1,2,3,4}.

Program:

``````import sys
sys.setrecursionlimit(10**9)

def fixHeight(nod, par, gr, H):
isleaf = True
for cnod in gr[nod]:
if cnod == par:
continue
isleaf = False
fixHeight(cnod, nod, gr, H)
H[nod] = max(H[nod], 1 + H[cnod])
if isleaf:
H[nod] = 1

def getFarthest(node, gr, n1):

do = [False]*(n1+1)
fdrr = -1
dur = None
que = [(node, 0)]
do[node] = True
while que:
nod, dis = que.pop(0)
if fdrr < dis:
fdrr = dis
dur = nod
for cnod in gr[nod]:
if do[cnod]:
continue
do[cnod] = True
que.append((cnod, dis+1))
return dur

def breakIntoLinesss(nod, par, gr, li, n1, cur):
H = *(n1+1)
fixHeight(nod, par, gr, H)
dfs(nod, par, gr, H, li, 1)

def dfs(nod, par, gr, H, li, cur):
isleaf = True
mx = 0
for cnod in gr[nod]:
if cnod == par:
continue
isleaf = False
mx = max(mx, H[cnod])
if isleaf:
li.append(cur)
return
c = 0
for cnod in gr[nod]:
if cnod == par:
continue
if H[cnod] == mx and c == 0:
dfs(cnod, nod, gr, H, li, cur+1)
c+=1
else:
dfs(cnod, nod, gr, H, li, 1)

for case in range(int(input())):
n1, k = map(int, input().split())
gr = [[] for i in range(n1+1)]
for i in range(n1-1):
u,v = map(int, input().split())
gr[u].append(v)
gr[v].append(u)

if k==1:
print(1)
u = getFarthest(1, gr, n1)
li = []
breakIntoLinesss(u, 0, gr, li, n1, 1)

li.sort(reverse = True)
size = 1
total = 0
i = 0

while total < k:
size += 1
total += li[i]
i+=1
print(size)
``````