codeforces-scrape

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

2183D1.md (2798B)


      1 Source: https://codeforces.com/problemset/problem/2183/D1
      2 
      3 D1. Tree Coloring (Easy Version)
      4 
      5 time limit per test
      6 
      7 2 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 This is the Easy version of the problem. The difference between the versions is that in this version, you are only required to find the minimum number of operations. You can hack only if you solved all versions of this problem.
     22 
     23 You are given a rooted tree$^{\text{∗}}$ consisting of $n$ vertices numbered from $1$ to $n$, where the root has index $1$, and each vertex is initially white. Define $d_i$ as the distance from the root to the $i$-th vertex. You can perform the following operations any number of times:
     24 
     25 1. Select a subset $S$ of white vertices such that no two nodes in $S$ are connected by an edge, or have the same distance to node $1$. Formally, $S$ should satisfy for all $x,y\in S$ and $x\neq y$, $d_x\neq d_y$ and there are no edges between $x$ and $y$.
     26 2. Color the vertices in $S$ black.
     27 
     28 Your job is to find the minimum number of operations required to color the full tree black.
     29 
     30 $^{\text{∗}}$A tree is a connected graph without cycles. A rooted tree is a tree where one vertex is special and called the root.
     31 
     32 Input
     33 
     34 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.
     35 
     36 The first line of each test case contains a single integer $n$ ($2\le n\le 2\cdot 10^5$) – the number of vertices in the tree.
     37 
     38 The $i$-th following $n-1$ lines contain two integers $u_i$ and $v_i$ ($1\le u_i,v_i\le n$, $u_i\neq v_i$) – the ends of the $i$-th edge.
     39 
     40 It is guaranteed that the given edges form a tree.
     41 
     42 It is guaranteed that the sum of $n$ over all test cases doesn't exceed $2\cdot10^5$.
     43 
     44 Output
     45 
     46 For each test case, output the minimum number of operations on a new line.
     47 
     48 Example
     49 
     50 Input
     51 
     52 ```
     53 10
     54 
     55 5
     56 
     57 3 1
     58 
     59 1 2
     60 
     61 5 1
     62 
     63 4 1
     64 
     65 5
     66 
     67 3 2
     68 
     69 2 4
     70 
     71 2 5
     72 
     73 1 2
     74 
     75 5
     76 
     77 3 4
     78 
     79 4 1
     80 
     81 5 1
     82 
     83 1 2
     84 
     85 5
     86 
     87 2 5
     88 
     89 3 1
     90 
     91 2 1
     92 
     93 3 4
     94 
     95 5
     96 
     97 1 3
     98 
     99 1 5
    100 
    101 4 3
    102 
    103 2 4
    104 
    105 13
    106 
    107 2 1
    108 
    109 3 2
    110 
    111 4 2
    112 
    113 5 4
    114 
    115 6 3
    116 
    117 7 1
    118 
    119 8 5
    120 
    121 9 6
    122 
    123 10 4
    124 
    125 11 7
    126 
    127 12 8
    128 
    129 13 10
    130 
    131 10
    132 
    133 5 7
    134 
    135 8 1
    136 
    137 1 10
    138 
    139 2 8
    140 
    141 8 4
    142 
    143 9 4
    144 
    145 6 1
    146 
    147 5 3
    148 
    149 7 8
    150 
    151 10
    152 
    153 7 6
    154 
    155 3 7
    156 
    157 6 9
    158 
    159 7 1
    160 
    161 9 8
    162 
    163 5 1
    164 
    165 3 10
    166 
    167 9 2
    168 
    169 1 4
    170 
    171 10
    172 
    173 10 6
    174 
    175 2 8
    176 
    177 4 10
    178 
    179 7 5
    180 
    181 1 2
    182 
    183 7 10
    184 
    185 10 9
    186 
    187 9 1
    188 
    189 7 3
    190 
    191 10
    192 
    193 6 8
    194 
    195 9 7
    196 
    197 4 10
    198 
    199 5 9
    200 
    201 4 2
    202 
    203 3 8
    204 
    205 6 5
    206 
    207 1 5
    208 
    209 1 10
    210 ```
    211 
    212 Output
    213 
    214 ```
    215 5
    216 
    217 4
    218 
    219 4
    220 
    221 3
    222 
    223 3
    224 
    225 3
    226 
    227 4
    228 
    229 4
    230 
    231 4
    232 
    233 3
    234 ```
    235 
    236 Note
    237 
    238 In the first test case, $d_1=1$ and $d_2=d_3=d_4=d_5=2$. We can show that we must perform at least $5$ operations because there are no two nodes that can be operated on simultaneously.
    239 
    240 In the second test case, we can show that the least number of operations required to color the full tree is $4$. One way to do so is to color nodes $1$ and $3$ in the same operation, and all $3$ other nodes in their own operations.