codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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  ![](https://espresso.codeforces.com/0d867aa6ca1261344a53fb61ed151f444bcb0a9f.png) 
    125 
    126 After removing the edge $1$ — $3$, the tree will look as follows:
    127 
    128  ![](https://espresso.codeforces.com/aa63ee921b47137c69a9c33f9d84cccf85a386e5.png) 
    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$.