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.