CT42168

The Longest Trail of the Hidden bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the mountain city of Highreach, Aria the store warden keeps careful count of the bridges. Audit the season's records, every figure matters. 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 <= 2698; the input is a connected tree.

Example 1:

Input: 2651 1409 1989 1350 1929 425 975 447 846 471 756 431 1394 96 253 463 692 1616 1898 492 1062 1110 1183 302 1362 2231 2243 530 1145 1931 2364 41 61 93 189 195 199 341 1006 1073 2056 1089 1340 1791 2581 220 614 568 1556 1990 2126 7 94 142 726 1295 1334 561 1714 3 250 1490 1569 191 211 576 1361 1638 1816 72 1014 129 461 408 625 91 165 468 1238 164 288 1157 2138 90 160 107 204 29 60 363 2262 190 1318 871 1004 965 1308 349 454 1062 1614 63 149 772 2463 1084 1438 612 1023 489 2412 127 210 660 684 255 585 228 1707 332 2380 1579 2438 1430 2222 543 1063 454 2537 231 2106 135 191 42 534 1163 1471 1168 1321 673 1826 32 44 951 2151 125 309 382 2332 446 1535 160 1332 10 18 2083 2203 1187 2492 657 2074 962 1302 44 1954 376 672 164 195 104 2079 2135 2367 52 1002 56 951 237 2553 2017 2143 173 2587 298 1128…
Output: 33

Example 2:

Input: 946 210 808 181 374 13 59 113 633 30 656 312 752 63 276 2 3 695 942 13 148 60 101 467 727 169 719 132 733 11 17 52 168 3 16 895 896 329 772 4 35 533 930 164 345 70 242 773 861 143 494 220 261 300 327 26 99 101 212 362 500 529 828 538 726 445 584 99 338 41 60 96 328 88 98 199 806 474 932 169 190 542 750 44 179 480 669 309 736 143 630 113 185 86 354 47 118 271 452 370 832 105 636 3 19 20 253 430 812 70 113 674 738 549 598 77 362 20 53 30 651 26 746 639 677 353 631 191 200 9 62 257 825 239 673 154 521 59 404 362 764 449 810 70 160 6 45 76 269 103 262 472 905 67 523 36 156 808 813 16 75 359 469 622 647 128 199 23 38 215 367 87 257 75 525 718 887 27 47 40 110 293 395 69 121 23 144 124 139 172 701 61 536 138 436 11 130 147 254 186 228 214 279 13 339 727 751 574 692 55 850 168 193 10 330 26 77 38…
Output: 24

Example 3:

Input: 2276 1568 2253 1174 2228 157 318 819 1163 1455 1620 1232 1976 44 94 1025 1215 841 1458 300 625 679 1555 307 2034 313 881 1497 1956 91 505 63 793 509 2106 147 558 394 504 141 378 628 1509 1564 1578 175 614 146 173 115 145 554 1196 799 1874 780 1292 690 1475 904 2133 676 960 1167 1931 109 1837 53 100 188 884 194 825 1554 1917 267 926 357 979 533 2075 74 1349 198 980 8 816 507 526 268 1646 10 34 673 1384 920 1504 623 2174 822 1187 1025 1087 11 168 1060 1847 264 1525 230 696 1075 1448 719 898 345 542 20 223 830 1213 435 615 317 529 70 562 1428 1833 50 202 159 596 138 572 1632 2262 19 101 2010 2185 968 1647 493 2161 916 2014 352 811 620 968 1180 1189 223 295 670 705 2009 2151 941 1914 316 397 1588 1799 688 951 6 57 1142 1245 961 1358 608 987 555 1047 611 817 829 874 726 1444 685 1297 53 54 82 2…
Output: 32

Constraints:

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

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