Jun 5, 2021
CodeChef: June Challenge | Minimum Subtree Cover | Python, Java, C++ Solution
You are given a tree with nn vertices (numbered 1,2,…,n1,2,…,n) and an integer kk.
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 TT.
A subset SS of vertices is called good if every subtree containing all the nodes in SS has at least kk nodes.
Find the size of the smallest good subset.
Input
- The first line contains a single integer TT, the number of test cases. The descriptions of test cases follow.
- The first line of each testcase contains two integers, nn and kk.
- The next n−1n−1 lines each contains two integers uu, vv, denoting an edge between vertices uu and vv of the tree.
Output
- For each test case print in a single line, the minimum size of a good subset.
Constraints
- 1≤n≤1051≤n≤105
- 1≤k≤n1≤k≤n
- 1≤u,v≤n1≤u,v≤n
- The given edges for each test case form a tree.
- The sum of nn over all test cases is at most 106106.
Subtasks
Subtask #1 (30 points): 1≤n≤1031≤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 11: Consider the set S={1,6}S={1,6}.
The smallest subtree that contains both of the vertices in SS is the path between them (1→2→3→5→61→2→3→5→6) which contains 55 vertices. Hence for k=5k=5, the answer is 22.
Test Case 22: Consider the set S={2,3,4}S={2,3,4}.
The smallest subtree that contains these three vertices includes 44 nodes {1,2,3,4}{1,2,3,4}.
Solution
Due to copyright issues we won’t be able to update the solution here immediately. However you can download the code file from our telegram channel. So join our telegram channel for further updates. Keep tracking, the solution will be updated on this website soon.
Read more post Here
