CT49882

The Longest Trail Beneath Firewatch

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the caldera rim of Firewatch as Smith unrolls the day's manifest of routes. The tally will decide the next shipment. 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 <= 2787; the input is a connected tree.

Example 1:

Input: 210 111 115 46 64 79 96 91 119 8 181 96 140 87 197 50 148 58 86 1 2 110 158 10 134 15 76 4 114 38 81 49 93 71 205 68 126 135 180 108 206 98 179 195 204 4 6 17 40 14 48 135 170 101 120 61 92 160 175 2 10 118 182 142 155 58 108 21 133 174 193 31 37 22 118 85 94 112 147 18 65 24 51 108 122 48 207 18 26 166 177 65 99 72 199 3 33 3 18 23 100 95 139 6 11 46 73 128 160 65 146 119 163 91 157 187 188 8 109 9 168 115 154 9 90 82 84 53 67 64 79 56 112 39 110 49 101 13 25 21 45 180 184 37 87 170 196 30 145 83 183 48 186 25 200 70 74 44 121 11 35 41 44 1 106 123 192 24 77 106 117 18 57 20 24 40 55 127 132 114 191 112 198 128 153 94 178 37 42 153 172 96 138 130 156 104 151 11 19 98 152 22 136 73 129 8 23 48 165 51 127 72 189 46 78 14 69 5 39 17 72 19 28 3 82 4 5 111 187 128 202 112 162 9 111 127 164 40 …
Output: 18

Example 2:

Input: 2535 172 227 1271 1553 519 1010 1815 1852 964 2132 1107 2101 2075 2491 880 2481 542 2427 391 1463 1611 1921 859 2376 689 2496 896 2166 85 137 126 219 1105 2298 933 973 41 56 296 516 1320 2380 47 65 2057 2271 453 510 86 1659 1233 1891 327 929 25 284 511 1464 854 1442 1589 1854 109 179 391 432 699 1669 42 315 341 1005 703 857 701 809 404 1529 4 58 349 703 919 1992 1126 1767 231 702 29 895 39 712 42 70 1638 2051 1714 2482 445 1265 553 2183 177 1055 1441 1514 1031 1053 139 2202 151 1007 494 678 191 465 181 258 91 1496 675 2080 398 761 2262 2448 285 331 2085 2426 50 126 1018 1260 608 1880 27 625 1446 1956 836 1297 22 233 3 8 287 1264 580 1401 503 1258 523 1536 232 2345 492 646 324 375 164 587 778 1862 97 101 164 902 375 801 829 921 1577 1700 273 593 698 2379 398 1580 559 1287 757 982 519 693 18…
Output: 29

Example 3:

Input: 1826 227 1189 891 1608 117 235 244 731 458 939 383 1174 355 786 48 119 119 456 387 974 88 142 304 553 219 1367 102 188 108 1309 365 1079 82 409 1252 1742 387 846 243 275 1229 1445 939 1388 579 905 520 1022 135 463 3 522 477 600 222 878 136 458 147 183 823 1102 323 1467 433 1104 128 1776 1327 1664 462 740 603 1145 12 36 47 48 59 581 379 1218 382 447 31 286 159 551 1499 1679 194 954 216 574 64 65 355 626 362 1297 1064 1308 141 258 770 1749 44 1370 321 879 359 682 180 184 39 41 1659 1768 442 550 116 1708 836 1506 437 460 653 922 6 90 438 1416 344 439 346 1365 328 555 54 309 554 1016 300 1082 184 677 316 1101 356 1531 13 1589 125 245 1061 1342 823 1272 218 418 8 70 1282 1726 285 335 238 433 3 254 90 567 95 1493 294 352 751 1242 186 274 19 23 347 871 394 587 221 521 258 493 1215 1334 27 33 216 …
Output: 29

Constraints:

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

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