CT36404

Scribe's Ledger of routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the ferry landing of Crosswater, someone must compute the guild dues owed. This year the task falls to Scribe, armed only with the routes register. 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 <= 2735; the input is a connected tree.

Example 1:

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

Example 2:

Input: 1188 22 134 48 69 590 1107 426 453 87 491 841 1081 463 733 825 877 431 721 337 565 674 840 176 1139 666 981 137 1093 80 977 90 664 26 52 288 301 34 628 12 324 112 295 1 4 239 493 413 573 53 196 4 68 229 296 10 283 8 72 856 915 754 907 825 1186 36 225 92 523 135 193 330 447 597 768 266 789 6 401 578 754 405 728 382 563 309 1046 350 786 353 854 34 89 489 767 112 449 490 1166 704 718 589 748 422 537 367 1099 196 377 285 1148 591 658 54 280 166 808 59 667 61 625 248 289 123 201 43 179 469 865 390 398 595 1174 22 234 539 686 69 365 1048 1124 357 375 490 1083 71 90 31 43 366 812 46 64 294 342 46 888 308 329 325 790 242 613 166 480 256 609 161 205 290 956 10 646 297 395 140 604 213 711 62 200 236 945 284 525 152 162 270 751 43 285 27 360 16 367 113 474 271 1082 73 410 251 440 918 1188 245 975 482…
Output: 22

Example 3:

Input: 1774 215 1235 382 1096 320 604 121 667 342 375 78 874 393 1564 348 723 1100 1342 557 1682 394 798 134 247 89 177 9 170 235 562 161 436 3 90 99 259 123 1040 1070 1089 884 1245 248 329 82 1476 11 15 532 749 1087 1409 449 698 456 466 51 1022 146 282 19 729 1204 1703 33 76 84 220 351 514 1161 1283 445 504 199 266 313 327 836 1016 456 1203 111 188 621 1241 133 262 465 1337 345 438 366 1400 778 1178 442 673 197 1017 71 758 717 1055 836 1292 226 1660 584 1482 569 1398 1016 1501 162 883 990 1566 349 790 57 855 315 376 101 526 72 128 188 1013 459 1247 124 1467 3 8 15 1182 100 1589 133 354 875 928 1216 1613 165 308 16 95 54 784 1064 1570 566 1553 751 1374 88 1038 18 21 123 1311 922 1630 1004 1087 366 1771 198 263 11 493 17 83 331 1576 1026 1709 475 666 853 1350 164 645 701 1171 201 840 91 905 285 33…
Output: 27

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Scribe's Ledger of routes - MEDIUM Coding Problem | CodeTikki