CT52949

The Umber Longest Trail

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Parth found an old ledger of corridors in the depot attic at the peat bogs of Mossgrieve. 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 <= 3988; the input is a connected tree.

Example 1:

Input: 2293 452 840 1413 1520 1002 1613 447 2184 1495 2116 862 927 646 1006 434 1421 1481 1518 53 1917 2 4 178 1826 263 724 128 270 165 686 1555 1654 185 1908 133 503 16 28 1 2 226 1433 393 2082 474 1261 1536 2056 610 774 311 1595 111 819 1378 1700 171 785 652 1720 1064 1349 1279 1459 386 827 248 2105 410 677 147 162 803 1418 891 1039 642 1516 104 2229 319 968 244 615 187 214 824 1904 777 1194 21 1655 61 107 13 624 567 1424 108 160 291 1985 59 323 765 1918 1865 2028 32 36 488 866 345 1120 98 493 50 71 749 1245 388 1300 182 795 11 14 343 1360 720 1488 798 2064 563 2283 411 1041 1735 2234 749 1744 713 1059 1084 1530 1892 1900 98 254 76 88 380 2241 729 1568 1143 1698 713 1285 215 633 458 1276 1295 1554 28 1649 125 879 68 397 877 1674 200 831 659 2020 1788 2059 72 482 307 1443 1142 1769 587 1729 606 …
Output: 27

Example 2:

Input: 2191 187 322 124 1417 93 1529 40 1748 19 1331 203 347 144 414 41 729 168 1466 983 1113 1608 1736 180 315 128 614 1279 1406 25 547 325 544 526 1941 311 520 1288 2015 291 1246 222 568 1223 1380 745 2099 371 1413 1092 1458 718 1250 1214 2020 484 726 63 730 138 793 453 519 333 807 28 300 86 747 635 1268 119 2163 639 1766 675 1390 84 576 684 1195 415 686 379 1949 476 1361 942 1538 395 703 7 65 688 978 115 116 24 266 879 2145 879 1975 275 314 39 850 1715 1838 1280 1802 930 1880 679 1353 1291 1333 324 1687 1092 1346 392 1371 53 84 270 425 624 1021 177 899 406 418 1807 2097 1001 1271 57 566 392 441 1098 1854 34 312 532 1640 756 2135 138 161 1415 1889 1062 1659 187 1071 339 516 92 262 961 1079 220 479 1271 1298 299 1007 36 460 390 1918 47 96 1348 1953 290 366 69 122 276 329 106 138 840 861 710 1887…
Output: 29

Example 3:

Input: 2657 360 2055 457 1004 1573 2320 193 318 635 1734 1395 2014 335 1177 218 370 350 1229 524 2235 105 399 572 1134 216 711 513 1048 312 446 179 1158 721 959 640 1070 778 1239 1253 2337 542 1089 326 2164 363 1268 2269 2339 1106 1741 110 376 248 297 3 1248 1344 2383 312 1486 1177 1947 695 2205 418 1463 272 462 499 773 844 1449 11 12 1409 1739 409 583 156 1414 1537 2227 1502 2633 420 849 616 1015 1438 1732 626 648 187 1078 821 2026 7 510 669 1460 203 315 1138 2593 468 1006 49 471 1864 1919 319 702 680 2302 1533 2477 386 465 506 652 5 226 612 934 401 680 468 637 163 1313 195 1625 230 2105 7 94 561 1988 836 881 1467 1820 166 1381 53 1203 1237 1332 424 2012 2010 2242 220 1764 1680 2107 152 1909 892 903 357 836 267 953 173 499 311 1803 1732 2189 388 919 28 875 1711 2582 349 688 541 1574 510 684 310 …
Output: 32

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Umber Longest Trail - MEDIUM Coding Problem | CodeTikki