1946C.md (2443B)
1 Source: https://codeforces.com/problemset/problem/1946/C 2 3 C. Tree Cutting 4 5 time limit per test 6 7 3 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a tree with $n$ vertices. 22 23 Your task is to find the maximum number $x$ such that it is possible to remove exactly $k$ edges from this tree in such a way that the size of each remaining connected component$^{\dagger}$ is at least $x$. 24 25 $^{\dagger}$ Two vertices $v$ and $u$ are in the same connected component if there exists a sequence of numbers $t_1, t_2, \ldots, t_k$ of arbitrary length $k$, such that $t_1 = v$, $t_k = u$, and for each $i$ from $1$ to $k - 1$, vertices $t_i$ and $t_{i+1}$ are connected by an edge. 26 27 Input 28 29 Each test consists of several sets of input data. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of sets of input data. This is followed by a description of the sets of input data. 30 31 The first line of each set of input data contains two integers $n$ and $k$ ($1 \le k \lt n \le 10^5$) — the number of vertices in the tree and the number of edges to be removed. 32 33 Each of the next $n - 1$ lines of each set of input data contains two integers $v$ and $u$ ($1 \le v, u \le n$) — the next edge of the tree. 34 35 It is guaranteed that the sum of the values of $n$ for all sets of input data does not exceed $10^5$. 36 37 Output 38 39 For each set of input data, output a single line containing the maximum number $x$ such that it is possible to remove exactly $k$ edges from the tree in such a way that the size of each remaining connected component is at least $x$. 40 41 Example 42 43 Input 44 45 ``` 46 6 47 48 5 1 49 50 1 2 51 52 1 3 53 54 3 4 55 56 3 5 57 58 2 1 59 60 1 2 61 62 6 1 63 64 1 2 65 66 2 3 67 68 3 4 69 70 4 5 71 72 5 6 73 74 3 1 75 76 1 2 77 78 1 3 79 80 8 2 81 82 1 2 83 84 1 3 85 86 2 4 87 88 2 5 89 90 3 6 91 92 3 7 93 94 3 8 95 96 6 2 97 98 1 2 99 100 2 3 101 102 1 4 103 104 4 5 105 106 5 6 107 ``` 108 109 Output 110 111 ``` 112 2 113 1 114 3 115 1 116 1 117 2 118 ``` 119 120 Note 121 122 The tree in the first set of input data: 123 124  125 126 After removing the edge $1$ — $3$, the tree will look as follows: 127 128  129 130 The tree has split into two connected components. The first component consists of two vertices: $1$ and $2$. The second connected component consists of three vertices: $3, 4$ and $5$. In both connected components, there are at least two vertices. It can be shown that the answer $3$ is not achievable, so the answer is $2$.