Minimum Subtree Cover SUBTRCOV SOLUTION

by

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.
Subtasks
Subtask #1 (30 points): 1≤n≤103
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 = [0]*(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)

June Long Challenge 2021 Solutions

March Long Challenge 2021 Solutions

April Long Challenge 2021 Solutions

Codechef Long Challenge Solutions

February Long Challenge 2021

January Long Challenge 2021

November Challenge 2020 SOLUTION CodeChef

October Lunchtime 2020 CodeChef SOLUTIONS

RELATED :

Related :

Related :