CT45316

The Longest Trail of the Pearl roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the maple sugarbush of Saprun, Jarl records each roads in a worn leather ledger. The guild wants answers, not guesses. 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 <= 3049; the input is a connected tree.

Example 1:

Input: 2319 1422 2027 1223 1763 409 937 142 449 135 572 153 1713 340 1232 366 1930 35 287 108 682 810 1295 597 1233 413 2266 552 1661 180 213 1597 1601 9 329 366 525 167 2191 165 598 195 869 157 670 57 2021 753 1327 600 2122 1930 2286 616 947 163 455 1832 2263 1180 1411 664 997 1786 1847 1127 2193 160 776 168 566 1425 1591 1662 1896 1520 2010 408 766 31 51 91 387 1009 1389 675 1573 249 979 259 580 324 1758 1662 2290 151 264 768 1303 215 560 939 980 873 1167 13 891 1953 2045 396 1581 616 774 549 651 383 1934 911 1538 79 434 1092 2099 31 32 1103 1247 310 348 116 396 919 1170 157 536 225 363 372 489 754 1549 418 1347 362 1805 105 183 17 547 533 2000 1781 2264 526 1858 278 529 445 644 71 279 1112 1138 562 1027 337 741 192 1349 1322 1376 583 1969 314 1119 414 974 27 2274 1217 1476 1654 2318 287 2163 2…
Output: 27

Example 2:

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

Example 3:

Input: 1702 15 618 62 346 405 727 179 901 345 1038 354 1203 323 1226 417 455 491 1330 354 534 26 657 491 987 1171 1223 988 1593 412 1353 344 355 24 74 32 601 206 318 1123 1319 64 271 365 735 304 511 32 350 1231 1594 116 138 397 1188 165 1168 508 781 823 870 192 881 407 524 125 387 1122 1160 382 1473 18 773 470 563 150 360 598 602 260 348 254 351 94 104 730 936 263 1105 31 34 165 641 53 300 624 1355 62 76 1027 1299 1002 1340 336 1651 1111 1195 146 169 508 894 702 1051 448 805 77 585 196 204 867 1052 384 917 14 174 1131 1257 523 818 477 645 96 1228 189 1061 108 335 5 109 11 54 395 747 67 102 984 1609 54 339 1603 1667 103 155 52 103 610 1173 883 1437 1069 1577 452 974 394 861 15 154 486 624 746 943 503 698 849 957 653 742 239 638 13 31 1155 1428 419 745 409 425 287 605 298 939 252 385 47 1059 205 51…
Output: 29

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Longest Trail of the Pearl roads - MEDIUM Coding Problem | CodeTikki