CT39767

Mason and the Saffron roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Mason found an old ledger of roads in the greenhouse attic at the garden city of Petalbrook. The margin notes pose a precise question. Task: A tree has n nodes and n-1 unweighted edges. Print its diameter (in edges). Input format: First line: n. Next n-1 lines: u v. Output format: Print the diameter. Constraints: 1 <= n <= 2312; the input is a connected tree.

Example 1:

Input: 973 127 378 218 262 101 419 98 425 132 819 736 772 378 451 200 244 457 746 150 365 36 169 60 940 206 373 617 661 148 494 241 466 2 6 271 359 29 86 487 851 130 399 366 620 310 358 494 615 167 966 16 76 15 93 177 342 1 2 744 965 112 294 187 324 98 563 65 123 189 255 56 78 102 161 315 894 72 453 36 448 755 767 144 934 221 323 61 764 386 449 643 668 606 870 9 493 44 318 32 115 121 384 441 490 370 481 26 58 32 88 426 719 254 505 237 398 234 471 134 469 241 559 346 970 216 436 405 671 299 369 218 372 537 831 276 919 283 349 6 80 4 8 50 226 20 574 347 859 25 178 677 766 362 676 855 968 515 601 84 213 43 284 157 470 36 74 160 927 8 20 568 635 41 110 6 500 345 552 714 716 198 363 234 418 365 540 406 861 195 791 183 249 187 347 62 866 51 127 64 239 608 655 599 622 168 409 11 943 536 810 370 827 483 …
Output: 24

Example 2:

Input: 263 26 165 1 203 80 118 14 130 63 204 103 104 224 259 70 138 70 95 40 76 154 223 19 45 159 191 51 52 133 210 16 31 165 230 78 194 59 132 108 198 26 63 12 35 62 212 36 53 75 150 10 59 128 174 214 241 17 128 3 5 97 262 59 72 3 19 10 263 42 50 76 106 6 146 120 179 8 48 170 239 6 14 19 26 12 107 21 32 134 187 81 260 247 258 4 167 18 30 123 217 20 93 55 70 141 164 57 231 110 256 15 143 13 34 39 77 1 10 62 122 15 145 122 186 12 27 195 242 31 56 58 140 166 240 198 233 27 152 18 21 87 238 43 87 167 213 20 85 85 177 170 221 117 125 8 47 39 64 8 38 206 234 84 113 17 29 91 219 130 209 169 170 10 155 64 183 201 202 26 37 10 68 59 244 150 196 55 94 176 235 70 232 33 90 1 2 118 172 59 91 10 237 5 25 45 111 56 136 15 41 81 247 54 134 8 12 11 18 240 252 12 124 56 109 213 220 11 105 10 129 233 248 10 20 45…
Output: 19

Example 3:

Input: 361 77 172 67 189 27 306 63 79 314 361 293 344 48 256 158 301 37 90 14 144 53 114 232 329 74 116 6 7 13 50 3 326 99 160 8 10 114 155 103 266 163 214 328 336 38 120 273 324 9 29 188 268 230 349 8 119 9 82 96 304 207 251 19 58 2 163 1 2 15 44 13 16 41 203 79 102 111 221 70 103 172 191 104 118 46 108 6 19 119 156 135 350 62 136 33 278 196 269 266 309 77 147 27 57 95 253 16 106 33 65 85 167 159 212 246 334 12 49 253 255 1 3 207 211 26 61 11 134 170 230 44 92 16 347 60 275 1 33 267 331 81 248 177 280 3 133 79 239 43 67 8 13 2 4 190 208 314 340 64 277 59 93 67 197 201 236 50 265 87 91 18 25 7 276 207 312 108 122 171 307 100 176 64 271 9 23 138 210 24 88 58 165 35 139 50 325 107 169 245 337 208 316 105 159 225 286 23 45 73 218 20 243 35 335 188 270 64 181 23 129 93 195 3 27 25 40 24 171 97 149 1 …
Output: 22

Constraints:

1 <= n <= 2312; the input is a connected tree.

Loading...
Test Cases:No test cases
No test cases available.