CT40440

The Longest Trail of Saffronia

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Asha the surveyor watches over the spice bazaar of Saffronia's stores of corridors. A careful computation stands between order and chaos. 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 <= 2761; the input is a connected tree.

Example 1:

Input: 404 65 393 92 142 122 150 306 344 120 330 195 341 95 263 154 236 156 291 265 337 327 339 183 327 18 72 12 13 12 251 235 343 38 129 160 292 17 45 66 390 15 36 71 124 11 14 38 168 261 398 168 385 91 219 40 178 39 188 210 248 45 58 97 190 199 288 173 223 42 340 169 376 24 238 163 215 282 322 211 342 15 346 23 192 29 350 52 261 58 227 16 38 179 282 8 139 2 3 32 136 186 358 68 311 235 287 73 133 4 8 32 43 71 270 105 309 290 360 45 49 6 16 194 234 132 159 57 68 30 65 44 131 76 90 112 144 10 267 44 146 53 61 72 370 81 174 3 15 81 98 32 66 11 258 184 380 206 329 18 47 38 51 28 41 23 233 13 54 48 156 3 21 7 77 156 355 148 389 37 255 98 115 169 362 280 283 7 59 78 306 57 379 46 378 2 5 307 310 78 202 20 74 103 167 28 141 104 208 21 57 32 111 38 81 36 180 87 128 288 290 28 304 268 308 20 140 4 105 14…
Output: 18

Example 2:

Input: 1036 64 867 164 364 481 971 642 779 2 355 195 989 138 409 50 71 11 249 776 878 309 324 297 328 614 1006 469 671 155 232 95 235 267 885 403 423 47 574 474 614 359 812 42 104 346 482 274 585 641 787 66 125 44 51 105 139 469 876 722 961 539 637 403 512 27 290 33 110 196 268 444 508 423 839 451 803 151 369 112 701 356 514 48 61 105 187 42 77 116 505 388 443 8 979 49 910 405 520 9 45 219 963 178 576 414 431 377 724 736 925 223 427 584 636 56 164 20 460 127 224 525 635 135 203 14 41 279 642 209 475 791 811 901 967 2 97 56 282 55 112 89 519 359 365 204 641 654 863 574 621 331 523 243 601 15 113 362 711 85 1013 53 69 304 870 683 729 37 109 117 799 122 191 149 246 91 605 341 353 830 917 21 432 50 100 38 827 426 714 157 166 22 52 43 135 153 824 247 256 98 456 581 705 10 14 181 502 188 333 56 162 187…
Output: 30

Example 3:

Input: 417 13 23 1 80 40 385 83 171 168 261 57 94 6 228 176 296 47 227 51 71 138 229 81 89 174 198 15 31 167 378 165 281 249 383 87 267 88 172 75 143 71 147 81 100 175 284 41 69 74 101 4 155 101 125 57 58 320 356 3 4 105 166 35 54 153 376 10 78 188 405 2 3 48 110 4 7 8 39 47 184 64 209 87 359 157 240 41 112 78 133 115 221 119 206 45 46 46 51 4 194 294 295 69 266 22 297 44 282 13 55 81 137 144 321 14 41 14 18 89 108 216 396 201 276 159 340 31 293 71 84 59 342 67 223 57 412 51 73 178 303 277 389 4 222 81 106 172 237 14 85 78 145 133 306 10 271 23 241 248 279 228 307 44 156 79 201 74 97 357 370 18 210 266 398 47 103 17 70 115 193 57 260 68 162 166 292 148 163 116 380 161 178 21 197 20 317 22 35 104 402 202 247 310 377 119 328 28 139 1 131 206 403 22 136 133 226 36 289 223 334 10 24 159 207 115 339 2…
Output: 21

Constraints:

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

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