CT51777

Mira and the Longest Trail

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Mira found an old ledger of bridges in the kitchen attic at the frontier camp of Duskwood. 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 <= 2004; the input is a connected tree.

Example 1:

Input: 1261 1242 1252 273 651 151 270 214 821 174 317 983 1144 746 1233 127 152 391 676 146 907 702 853 34 300 495 800 165 311 93 935 611 892 540 1106 821 1031 348 1081 681 856 315 332 772 1253 247 1087 437 454 95 455 108 1186 136 176 951 1094 5 235 974 1153 62 747 16 232 347 857 89 516 32 47 63 116 470 1010 151 792 651 696 668 896 18 253 46 637 1141 1162 897 1033 51 141 75 119 376 448 117 203 294 963 185 518 55 58 96 703 58 68 159 362 340 514 498 680 483 1116 342 1064 858 1119 27 29 270 440 811 1055 161 628 149 920 26 901 786 1150 460 1044 511 634 307 432 339 1032 139 413 21 745 5 24 88 1043 904 942 683 1059 329 631 116 683 338 357 139 227 194 472 80 174 156 335 27 673 590 891 878 1147 308 813 1 2 121 231 1095 1118 533 893 35 65 277 1071 47 123 329 462 171 172 104 132 5 381 2 185 2 81 192 699 17…
Output: 27

Example 2:

Input: 695 41 195 314 394 89 112 383 463 524 653 114 475 1 107 128 438 46 76 153 191 193 450 576 623 11 78 130 193 125 245 91 221 196 341 36 357 388 488 269 418 76 121 11 40 262 391 76 369 443 444 207 372 106 175 242 335 274 572 373 471 378 555 10 235 266 533 53 172 318 361 164 275 438 440 106 140 62 161 28 242 79 97 121 386 116 588 378 496 12 104 213 309 132 451 251 563 16 334 215 554 80 90 199 456 40 479 115 363 361 410 142 200 211 265 129 329 143 528 36 183 188 259 75 91 10 328 329 579 335 408 460 648 424 655 169 504 10 422 2 8 164 283 12 149 286 336 590 673 307 445 232 236 2 4 583 645 584 610 304 576 614 654 5 14 18 37 6 32 4 79 184 559 177 650 212 518 1 2 158 332 51 52 76 599 278 553 11 12 17 308 56 353 41 312 72 497 115 125 127 527 224 269 44 133 176 360 48 139 26 64 33 281 269 452 254 295 …
Output: 23

Example 3:

Input: 52 1 3 7 22 23 46 21 24 5 21 9 12 5 7 16 30 12 44 21 33 3 50 1 2 13 23 21 47 3 27 3 31 17 49 1 4 2 13 6 18 1 5 14 16 10 11 44 48 7 37 15 41 48 51 39 45 4 25 4 8 4 43 16 17 29 40 1 9 14 38 34 35 9 19 4 15 9 42 25 34 7 32 22 26 4 6 36 39 5 10 5 14 16 28 22 52 11 20 11 36 9 29
Output: 11

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Mira and the Longest Trail - MEDIUM Coding Problem | CodeTikki