Gardener and Tree solution codeforces
-
For Solution
Click Here!
A tree is an undirected connected graph in which there are no cycles. This problem is about non-rooted trees. A leaf of a tree is a vertex that is connected to at most one vertex.
The gardener Vitaly grew a tree from nn vertices. He decided to trim the tree. To do this, he performs a number of operations. In one operation, he removes all leaves of the tree. Gardener and Tree solution codeforces
Example of a tree.
The result of applying the operation “remove all leaves” to the tree.- applying an operation to an empty tree (of 00 vertices) does not change it;
- applying an operation to a tree of one vertex removes this vertex (this vertex is treated as a leaf);
- applying an operation to a tree of two vertices removes both vertices (both vertices are treated as leaves).
Vitaly applied kk operations sequentially to the tree. How many vertices remain?
Gardener and Tree solution codeforces
The first line contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases. Then tt test cases follow.
Each test case is preceded by an empty line.
Each test case consists of several lines. The first line of the test case contains two integers nn and kk (1≤n≤4⋅1051≤n≤4⋅105, 1≤k≤2⋅1051≤k≤2⋅105) — the number of vertices in the tree and the number of operations, respectively. Then n−1n−1 lines follow, each of them contains two integers uu and vv (1≤u,v≤n1≤u,v≤n, u≠vu≠v) which describe a pair of vertices connected by an edge. It is guaranteed that the given graph is a tree and has no loops or multiple edges.
It is guaranteed that the sum of nn from all test cases does not exceed 4⋅1054⋅105.
Gardener and Tree solution codeforces
For each test case output on a separate line a single integer — the number of vertices that remain in the tree after applying kk operations.
Gardener and Tree solution codeforces
input
6 14 1 1 2 2 3 2 4 4 5 4 6 2 7 7 8 8 9 8 10 3 11 3 12 1 13 13 14 2 200000 1 2 3 2 1 2 2 3 5 1 5 1 3 2 2 1 5 4 6 2 5 1 2 5 5 6 4 2 3 4
Gardener and Tree solution codeforces
7 1 4 3 5 1 1 3 6 1 1 7 2 1
Gardener and Tree solution codeforces
7 0 0 3 1 2
Gardener and Tree solution codeforces
The first test case is considered in the statement.
The second test case contains a tree of two vertices. 55 operations are applied to it. The first one removes one of the vertices, the other operations do not change the tree.
In the third test case, a tree of three vertices is given. As a result of the first operation, only 11 vertex remains in it (with the index 22), the second operation does not change the tree.
-
For Solution
Click Here!