CT39502

Dev's routes Longest Trail

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Dev found an old ledger of routes in the timber yard attic at the wren hedges of Thimblewick. 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 <= 2601; the input is a connected tree.

Example 1:

Input: 1168 80 82 365 411 28 522 175 505 376 780 31 43 791 984 342 661 220 470 226 360 120 144 182 319 32 182 433 808 868 953 278 728 501 659 173 244 381 589 171 819 494 852 33 54 351 1035 30 1063 769 919 6 25 50 1003 394 952 577 1041 31 218 669 680 848 909 67 354 118 1022 31 91 56 280 95 402 1 445 172 219 3 245 20 270 258 758 350 645 82 726 264 1002 932 1053 182 348 510 1087 167 356 10 910 95 933 39 342 606 869 196 744 176 196 544 907 448 532 8 23 12 14 453 527 239 639 159 279 185 510 636 665 37 261 296 1122 233 571 8 135 47 141 842 930 15 150 147 262 42 714 309 835 792 964 201 747 20 462 91 226 173 385 768 1135 310 484 8 776 591 965 28 85 647 1031 9 16 265 983 718 859 83 90 529 936 859 1068 1 916 636 679 605 1059 118 1141 305 557 656 993 6 21 113 529 270 316 361 742 128 179 809 978 109 156 220 …
Output: 26

Example 2:

Input: 1450 4 1142 558 651 100 865 1070 1399 328 612 123 222 385 1318 352 371 262 736 419 618 221 235 67 1162 268 921 313 960 222 879 33 38 759 922 50 387 109 225 780 1126 727 1181 1015 1165 231 620 298 525 381 892 718 1089 57 861 120 1341 121 200 9 83 555 877 984 1002 312 327 386 390 129 1150 177 1159 78 316 41 484 105 544 772 1211 1025 1300 30 49 703 1007 228 831 787 1019 55 193 86 239 802 1036 9 216 162 272 615 1415 361 871 766 1029 727 869 212 995 496 856 276 1423 36 108 562 1311 102 408 78 594 976 1228 23 29 275 335 130 1329 1211 1254 282 627 87 171 368 1417 421 1370 586 1401 1393 1397 251 889 798 1381 107 1011 305 738 293 363 778 880 28 470 483 718 211 963 1379 1411 263 1134 1244 1272 191 709 2 3 434 778 543 659 897 1251 373 670 137 981 137 214 104 226 360 959 205 472 89 971 443 630 3 8 120…
Output: 26

Example 3:

Input: 2030 13 89 304 1866 498 867 1162 1753 353 1013 243 1873 411 427 866 1393 120 265 156 1185 1283 1646 194 455 726 1936 725 1860 775 1410 317 1909 7 770 315 521 343 537 911 1358 1 133 7 79 1338 1905 1006 2000 10 103 384 952 73 1414 25 584 431 579 827 1195 904 1347 805 1761 1586 1690 29 237 890 1681 316 1009 47 70 7 64 1121 1511 46 600 460 955 1 2 157 201 546 642 348 381 233 1125 177 587 62 1148 143 355 129 1499 25 162 25 332 53 510 44 45 1098 1103 1911 1966 174 347 297 456 44 1277 191 1329 642 1529 733 988 1734 1948 448 872 56 226 870 1779 1378 1833 161 223 32 748 432 610 209 373 365 973 3 124 1002 1071 13 1802 885 1386 898 1043 303 1342 80 90 455 1728 1238 1321 71 167 39 1297 471 737 230 436 341 1892 408 809 280 858 1097 1200 788 1598 821 866 303 423 570 1501 65 344 591 601 12 534 131 326 9 …
Output: 31

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Dev's routes Longest Trail - MEDIUM Coding Problem | CodeTikki