CT36164

The Caravanrest Longest Trail

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Fiora found an old ledger of roads in the dairy attic at the dune sea of Caravanrest. 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 <= 1593; the input is a connected tree.

Example 1:

Input: 904 148 685 395 739 162 307 180 497 92 233 73 688 72 125 4 7 298 714 90 245 88 838 198 508 76 293 138 169 428 885 502 762 36 224 154 647 462 487 347 731 108 140 101 297 274 832 440 619 25 209 731 766 568 648 298 722 38 104 60 724 169 336 66 154 113 501 140 361 154 276 82 91 309 581 457 840 14 23 148 632 492 538 68 135 614 670 7 280 143 370 73 791 127 210 4 6 181 865 648 772 52 60 92 161 394 564 172 719 142 586 82 246 93 610 352 888 413 548 8 10 265 752 317 329 146 175 123 447 458 666 223 834 457 775 381 723 402 750 169 431 556 833 561 780 1 223 45 64 11 105 81 407 172 353 305 886 178 678 737 795 14 85 93 102 16 313 29 168 25 43 6 901 207 365 171 509 626 842 56 122 345 426 848 873 470 680 5 265 301 322 585 605 412 438 308 327 135 829 140 258 631 890 294 454 153 180 11 49 247 283 352 800 455…
Output: 26

Example 2:

Input: 854 239 713 386 542 12 49 434 692 78 152 7 397 49 545 114 656 387 504 66 496 34 54 127 360 521 526 130 478 132 541 620 816 287 573 51 94 126 221 24 285 681 696 94 669 526 636 297 308 230 657 299 327 201 555 560 617 79 509 421 477 306 442 61 150 217 718 177 423 555 574 373 377 121 182 323 358 568 763 449 806 94 119 229 606 190 195 90 121 106 349 152 529 337 717 14 58 706 751 44 625 199 267 44 205 15 32 471 838 792 811 326 756 174 728 453 722 22 774 619 850 46 65 116 255 183 761 28 100 684 843 96 533 39 67 313 618 53 510 13 147 105 672 20 74 15 407 520 849 76 279 291 443 279 491 188 773 295 386 137 553 92 137 176 595 226 497 5 27 313 840 663 831 114 361 14 307 12 207 9 86 164 439 96 109 623 742 458 624 225 233 287 666 255 768 35 770 552 809 25 41 119 549 34 73 176 394 455 824 74 120 397 769 …
Output: 28

Example 3:

Input: 1223 366 457 162 599 3 94 1105 1188 338 443 9 608 876 1122 13 62 440 869 479 648 118 403 86 1043 190 398 6 439 407 1107 202 522 153 329 716 756 117 531 190 865 178 251 509 557 679 1098 150 1135 107 556 131 773 103 1194 57 324 390 647 197 401 177 238 95 812 387 716 30 876 70 104 827 1137 546 988 243 922 414 540 84 161 374 765 577 743 651 721 657 814 1125 1177 86 103 54 237 811 1125 13 14 2 19 405 1164 800 910 463 577 15 1038 4 1074 341 1141 1189 1190 27 801 183 285 59 275 412 424 97 1175 13 22 355 784 85 152 788 882 246 352 70 704 68 102 232 463 496 809 411 786 8 20 606 1007 631 1220 92 411 531 1013 145 349 60 91 188 353 68 816 562 665 2 55 147 1099 74 1210 473 737 389 418 256 616 201 1172 13 250 885 1216 297 567 357 718 271 1193 303 376 506 1089 132 478 126 712 188 549 227 930 304 590 353 …
Output: 26

Constraints:

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

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