CT50803

Jeweler and the Sable routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the mining town of Ironvein opens only for a perfect tally of routes. Jeweler means to find out. 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 <= 1375; the input is a connected tree.

Example 1:

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

Example 2:

Input: 832 173 192 48 193 316 774 751 782 12 15 97 515 75 97 711 754 110 241 148 157 666 776 279 340 677 693 12 41 137 781 215 297 376 733 616 777 582 744 59 207 274 787 445 583 8 158 276 748 263 321 46 106 211 553 146 349 20 27 212 563 196 352 97 111 402 586 72 114 411 617 272 304 306 339 548 773 48 85 291 719 540 650 44 110 456 484 44 55 69 152 779 803 396 479 604 621 65 585 70 148 13 65 76 490 578 717 15 24 42 346 299 398 247 488 352 634 25 26 203 362 12 125 220 267 514 832 262 389 12 25 28 723 263 531 255 405 15 91 142 570 74 551 197 466 30 537 442 581 466 604 29 489 265 536 361 643 124 749 31 254 260 601 715 741 155 262 73 403 150 507 149 216 347 574 34 293 238 285 126 301 13 218 246 576 171 287 24 187 107 691 21 203 32 43 218 706 125 279 503 654 54 736 332 659 314 423 21 526 596 697 368 789…
Output: 22

Example 3:

Input: 716 565 629 533 583 25 561 574 600 13 128 39 52 144 231 384 655 295 503 222 483 405 433 32 115 53 238 128 160 273 467 496 581 13 76 423 436 118 159 42 143 555 560 54 122 105 712 80 84 325 714 62 112 322 490 177 457 521 534 556 582 8 23 28 324 556 651 323 439 514 670 103 641 38 133 3 33 151 154 55 538 87 529 190 224 414 535 117 379 46 88 192 247 221 222 104 326 149 514 115 476 130 223 12 19 89 265 424 530 409 453 154 220 97 387 116 695 597 701 1 217 22 450 182 279 57 249 86 202 628 692 80 343 33 642 34 105 179 242 17 228 56 57 53 55 26 67 43 103 61 75 139 456 231 516 472 576 448 594 317 404 5 65 29 521 1 408 112 248 154 440 5 8 78 595 520 693 123 153 115 506 31 344 105 330 210 410 62 81 241 542 175 194 65 151 189 282 117 124 130 191 161 573 9 449 97 427 184 216 249 507 105 116 40 306 270 34…
Output: 24

Constraints:

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

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