CT54680

The Longest Trail of the Shimmering bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The dispatch writer Gardener has been asked to compute the guild dues owed. On the desk lies a long table of bridges readings. 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 <= 2801; the input is a connected tree.

Example 1:

Input: 236 119 206 19 89 11 18 8 94 77 149 13 53 67 160 110 202 23 37 113 164 74 130 1 91 2 52 19 92 20 179 4 58 2 5 121 218 2 3 19 158 123 233 3 61 31 106 152 217 148 178 116 129 54 205 90 193 46 48 115 156 10 64 172 199 42 83 29 54 73 88 146 185 20 38 13 222 37 225 20 25 50 167 99 161 101 191 47 122 120 135 2 101 81 133 3 4 13 17 122 207 87 159 51 105 97 139 104 157 86 103 136 146 90 150 3 16 100 126 7 12 34 50 124 148 99 183 24 69 1 21 19 39 87 111 22 36 17 23 162 187 14 44 57 110 96 236 11 128 38 152 118 143 25 33 100 104 115 230 52 155 102 172 52 151 3 7 48 51 128 182 35 140 76 134 25 67 48 176 20 31 196 212 139 196 95 108 44 123 46 71 35 49 3 28 70 142 61 127 92 107 4 59 111 117 11 45 113 165 17 41 163 223 4 171 195 227 42 93 108 189 44 221 3 19 11 24 215 226 14 188 105 180 47 136 152 174 1…
Output: 23

Example 2:

Input: 937 3 8 506 581 534 576 121 560 443 584 176 647 604 622 838 875 3 38 493 569 260 393 223 749 645 753 357 447 50 900 410 872 54 810 758 929 109 625 675 913 765 773 636 745 139 281 789 838 145 934 511 807 111 545 467 804 167 439 82 220 360 487 152 334 146 681 332 358 367 863 62 214 33 39 476 593 256 368 111 442 326 382 216 677 127 706 118 623 129 149 632 687 30 179 86 87 599 915 287 419 64 380 130 649 72 125 28 269 140 172 3 615 550 754 439 470 139 602 23 27 230 357 445 843 76 134 100 200 57 98 300 496 77 97 638 673 176 406 479 859 97 219 63 856 403 541 16 772 55 477 71 651 19 287 523 708 302 425 192 303 491 916 196 776 88 565 213 906 280 530 130 835 22 230 5 11 18 327 33 43 157 288 521 919 273 756 562 813 80 112 243 454 452 459 296 536 37 201 152 599 123 878 107 375 210 443 361 370 177 240 …
Output: 26

Example 3:

Input: 985 94 114 168 406 808 822 516 786 28 48 10 177 357 504 123 473 531 731 49 733 261 477 428 495 191 267 217 283 299 588 3 6 162 963 65 127 207 359 36 39 95 256 664 747 124 856 557 569 346 813 215 448 78 329 12 138 67 72 1 75 68 740 354 410 431 765 80 957 186 608 117 126 564 802 27 156 290 470 77 183 44 341 358 964 89 140 60 130 134 201 330 618 683 790 537 900 417 632 174 209 42 58 598 646 52 160 80 239 117 171 127 479 306 360 336 951 30 378 5 17 278 848 220 690 552 691 141 666 118 229 26 834 289 934 443 457 480 527 508 852 41 52 46 83 262 688 181 718 77 161 179 234 13 70 239 345 586 708 234 336 432 451 429 906 298 462 249 621 526 866 275 810 51 98 468 980 313 404 145 599 92 313 608 897 145 616 272 405 317 363 239 791 125 317 616 847 290 453 141 265 391 533 627 777 584 776 17 248 197 296 647…
Output: 25

Constraints:

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

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