CT51096

Lamplighter's Ledger of roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the poppy fields of Scarlet Plain opens only for a perfect tally of roads. Lamplighter means to find out. 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 <= 1020; the input is a connected tree.

Example 1:

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

Example 2:

Input: 221 146 159 106 174 13 31 13 50 6 30 21 58 5 11 10 15 63 175 22 64 91 161 29 163 157 180 12 70 62 126 77 172 4 46 9 130 84 96 116 188 62 66 25 101 38 59 6 14 9 23 2 3 122 171 12 215 12 26 15 114 28 118 22 32 41 162 85 88 60 73 7 17 131 158 33 36 19 20 51 108 74 211 36 60 176 197 26 112 61 109 211 216 90 94 22 100 1 24 48 144 20 34 7 19 92 210 10 37 93 151 11 199 55 69 16 82 26 85 9 45 6 12 98 120 173 179 12 38 11 201 9 43 12 76 2 166 90 131 161 168 21 33 176 178 122 128 20 119 54 173 62 156 56 72 2 167 106 125 13 213 59 71 72 115 55 184 71 83 10 217 77 133 2 129 36 117 33 134 18 98 48 157 3 18 21 42 61 142 174 212 14 16 62 143 23 79 69 86 10 67 69 193 64 187 52 208 199 221 4 48 2 8 12 92 46 137 45 105 54 90 144 183 41 145 3 9 30 147 4 150 4 21 72 124 23 25 7 186 101 132 43 74 140 169 79 11…
Output: 16

Example 3:

Input: 1009 585 907 278 465 846 954 451 649 588 639 59 573 9 115 388 642 503 933 173 807 5 38 87 553 581 924 364 878 284 567 193 283 110 900 237 930 58 122 131 381 3 630 201 313 58 289 437 964 272 329 144 182 92 113 612 738 136 504 278 869 80 798 576 610 63 106 196 410 14 300 79 167 62 955 125 261 180 620 57 856 148 200 158 229 21 242 570 725 133 303 705 799 309 400 74 833 227 426 131 178 371 389 57 244 7 127 18 88 143 276 200 860 2 112 110 326 181 395 247 417 33 219 128 271 328 394 194 438 523 899 194 477 580 881 126 201 779 994 711 997 59 175 3 4 36 84 716 796 188 650 358 508 60 371 654 656 27 29 485 541 5 6 154 375 215 922 84 353 379 747 791 962 13 507 133 171 180 472 463 499 389 446 154 284 68 69 205 341 443 511 588 651 319 854 44 293 175 340 31 211 288 301 73 136 458 872 72 161 13 393 186 33…
Output: 21

Constraints:

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

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