CT40026

The Longest Trail Beneath Sandspire

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the desert outpost of Sandspire, Curator the scribe keeps careful count of the corridors. Prepare the expedition manifest, 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 <= 3368; the input is a connected tree.

Example 1:

Input: 2292 151 1234 762 2270 1125 1793 1363 2053 319 477 26 99 167 1010 110 183 34 125 37 98 1174 1283 1978 2078 1587 2245 1647 1728 81 2239 1246 1557 1775 1856 491 1146 678 1338 1785 2103 25 1593 13 843 151 651 593 1534 20 731 134 572 1996 2030 1787 1922 15 16 998 1721 810 1094 380 829 781 1980 736 1489 426 1818 95 228 100 285 1269 1432 1104 2117 756 1918 158 2171 1194 1524 1036 1186 233 317 1242 1452 893 1016 140 948 63 266 184 1448 508 767 92 892 789 996 244 504 469 662 615 997 163 1652 809 1692 284 2261 177 580 273 1042 665 984 20 1462 96 233 1044 1132 973 2075 140 144 308 465 423 449 1421 1570 42 47 324 1587 477 1106 15 1514 50 65 107 1385 139 1131 390 1611 1357 2148 988 1738 1856 1914 852 1158 184 1183 1270 1484 42 2035 394 472 737 2108 728 1262 643 1031 1244 1422 409 842 198 1571 1278 208…
Output: 30

Example 2:

Input: 2367 129 781 1978 2366 615 894 703 1007 297 1667 17 59 1279 2136 66 95 1339 1596 447 1971 108 179 164 923 375 1445 40 91 289 1322 940 2314 372 770 57 611 340 428 82 968 436 1188 230 1828 564 2350 214 245 9 131 554 1294 1512 1871 557 2201 15 86 247 608 8 236 612 1153 240 699 764 1978 417 1688 1218 2032 476 650 242 349 1280 2306 1367 1495 1443 1666 874 1271 555 558 1427 1650 2066 2101 25 193 556 1507 185 300 56 322 338 415 1720 1813 467 1233 268 588 242 1612 1054 1617 2124 2360 499 511 296 874 277 982 94 247 5 270 130 495 231 2045 1286 2336 1384 2175 331 480 162 1764 167 329 1379 1630 668 1981 686 692 250 1520 1410 2312 436 1481 651 926 246 261 2048 2187 452 517 83 554 189 853 1533 1890 759 797 330 1458 11 533 101 801 187 1706 126 816 1464 1651 15 525 63 1214 814 2141 352 2216 421 808 148 17…
Output: 26

Example 3:

Input: 548 399 421 329 400 112 213 10 74 137 163 133 442 79 140 246 270 268 503 114 188 1 3 186 255 106 334 82 219 346 547 269 491 423 449 22 25 233 263 98 323 10 301 60 80 229 236 136 187 92 360 39 87 306 366 72 102 33 49 92 281 19 60 27 256 83 541 196 429 83 138 31 172 159 232 324 352 50 380 322 398 89 507 315 479 379 516 39 272 69 251 14 103 25 27 14 286 27 303 41 81 45 92 210 468 143 241 288 517 8 88 96 206 200 227 361 456 419 446 95 170 229 540 208 318 86 514 307 327 153 512 122 467 162 245 13 18 189 529 451 546 161 438 281 316 37 510 158 284 32 35 56 111 87 525 183 392 9 11 28 473 196 197 162 423 51 448 73 100 62 146 23 108 392 537 355 494 26 82 305 357 100 210 64 131 180 443 122 294 31 105 36 122 128 453 12 240 129 322 170 242 38 54 18 145 67 269 74 194 41 543 57 480 316 430 22 208 175 237…
Output: 21

Constraints:

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

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