CT42420

Emir's routes Longest Trail

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Emir runs the timber yard at the port of Emberfall. Today the books show a list of routes, and the numbers must be worked out before sundown. 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 <= 2793; the input is a connected tree.

Example 1:

Input: 2336 830 958 727 1082 546 2201 1178 2016 458 718 1972 2222 361 986 224 448 741 1418 1047 2054 444 517 935 1103 1812 2292 429 2117 969 1002 202 856 921 1689 1729 1949 1697 1741 114 370 702 1330 238 1141 257 357 70 1429 1141 1210 512 1457 1136 1480 51 1443 85 674 319 327 258 646 724 1994 81 88 1033 1501 465 795 77 91 1098 1460 342 664 962 1051 1174 2304 28 355 1513 1564 319 422 282 1439 185 774 316 1134 1967 1977 548 734 535 1207 1366 1986 794 1937 567 1758 408 1040 224 274 442 722 542 983 1619 2094 23 103 704 1951 400 1385 988 1496 889 1636 1227 1705 292 721 1723 2168 353 576 203 725 910 1504 1592 2115 768 2291 301 1320 1049 1557 575 1473 887 2322 1259 2153 1174 1956 1730 1939 162 694 308 2002 762 1264 317 1246 465 1024 155 394 440 1844 37 51 7 1740 12 1202 339 1555 1970 2204 758 1293 1141 …
Output: 30

Example 2:

Input: 117 1 53 3 4 17 23 57 82 57 63 3 5 63 76 30 55 92 99 23 40 21 70 87 98 32 64 16 83 3 18 30 39 93 111 53 110 1 3 44 113 34 71 6 25 9 19 6 20 49 96 2 34 1 16 50 61 24 49 78 87 14 58 24 92 30 106 83 86 7 24 62 74 35 36 58 97 27 102 58 100 17 35 25 41 5 31 20 22 54 60 53 88 2 93 19 42 50 52 4 103 97 116 21 33 64 94 7 9 80 112 40 47 21 46 33 45 22 50 28 29 5 6 29 90 69 84 11 26 3 117 24 38 1 2 8 69 110 114 24 85 43 68 1 12 22 95 76 77 36 54 5 56 21 59 6 44 75 101 9 43 1 28 39 48 13 27 9 17 39 72 24 30 4 8 57 107 50 51 7 37 84 108 4 13 5 21 39 62 42 89 45 80 27 104 7 10 55 75 19 66 80 91 40 81 26 78 69 109 4 65 97 105 7 15 7 11 21 57 64 67 23 79 8 32 2 7 62 115 67 73 6 14
Output: 15

Example 3:

Input: 2433 733 1915 1152 2376 351 519 72 638 494 634 1830 1911 8 141 1893 2244 374 620 781 1665 182 1463 68 715 1436 1778 483 1564 214 713 775 784 129 158 875 1327 1582 2037 597 1206 1135 1456 14 29 287 1072 1680 1695 797 1342 881 1381 6 928 6 140 1060 1387 1349 1537 188 192 266 1706 99 186 267 813 758 2039 67 1104 125 1173 712 1622 136 2197 1103 1720 707 1059 514 1699 206 222 29 1360 798 1365 771 1722 1 2072 669 1689 453 1650 935 1221 458 703 963 1941 1982 2001 327 552 125 1576 2238 2242 1230 2188 789 1084 1781 2294 188 280 354 494 96 857 286 2279 628 1130 1897 2005 1432 1877 765 946 110 448 4 33 28 381 131 1552 242 285 1818 2155 187 385 963 1311 186 380 594 1887 326 1006 1209 1300 394 651 771 1097 26 655 759 866 12 14 283 2370 1133 2247 1034 1392 484 2054 191 1578 388 926 496 2079 689 1851 615…
Output: 27

Constraints:

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

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