CT56695

Galen's canals Longest Trail

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Galen found an old ledger of canals in the timber yard attic at the boar woods of Tuskmore. The margin notes pose a precise question. 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 <= 3470; the input is a connected tree.

Example 1:

Input: 2612 41 1560 398 500 1126 1251 1036 2227 25 2202 1133 2092 1539 1711 854 869 616 746 583 1425 984 1353 1782 1984 309 333 1899 2585 31 1760 367 582 241 1983 831 1985 352 811 1490 2408 2051 2537 651 764 469 678 182 511 88 930 379 1340 1914 2402 455 2469 522 1542 21 1230 2 2513 633 2577 268 797 813 2297 639 1600 741 2135 1181 1790 600 1223 628 703 310 1178 936 1165 510 1279 988 1633 8 12 873 1592 697 722 11 501 407 411 196 1292 2266 2284 1206 1672 109 206 14 262 293 406 71 214 115 1567 1245 1651 1239 1461 2062 2285 118 423 8 169 762 2027 289 773 232 683 66 760 804 1943 305 723 860 964 41 1628 1235 2552 2169 2355 1591 2036 802 1242 330 1778 75 258 1641 2176 1007 2582 21 24 43 967 1661 2339 191 1538 609 1104 133 1048 324 450 682 2232 114 799 259 330 240 420 99 887 1007 2161 1720 1938 1871 1906 …
Output: 29

Example 2:

Input: 438 21 90 142 289 110 171 73 192 28 58 171 208 37 182 272 312 109 201 44 211 80 395 63 106 42 195 218 251 389 400 318 413 136 145 26 102 14 159 206 333 180 293 125 424 186 199 61 120 9 107 15 30 48 191 359 417 175 394 9 137 67 89 9 22 38 335 38 257 41 162 26 153 296 322 345 405 8 20 107 398 120 134 86 324 196 283 56 121 18 25 40 150 343 362 163 194 36 379 206 327 230 281 122 214 120 316 195 268 75 172 183 406 113 114 44 176 240 300 302 423 148 156 2 39 343 373 41 60 295 347 1 46 268 325 212 329 5 13 284 425 233 334 40 66 104 141 189 247 2 7 137 157 62 393 165 272 143 155 7 15 199 267 16 124 5 264 6 36 68 189 227 371 194 409 182 427 46 104 107 348 235 252 88 204 46 233 4 10 123 320 234 367 255 288 83 244 118 184 2 59 151 305 46 255 62 73 27 87 35 294 31 108 278 381 5 115 161 263 307 385 3 6…
Output: 21

Example 3:

Input: 1405 284 810 118 264 1005 1377 242 571 345 497 425 520 945 1380 1099 1208 266 607 1 3 514 1222 220 1113 243 687 442 1075 696 881 356 1288 479 709 26 40 72 493 430 1293 3 22 628 884 662 681 91 1024 265 905 208 736 66 465 69 358 125 422 756 1160 5 1098 564 798 4 973 95 163 421 490 309 754 269 307 8 733 106 173 633 887 41 746 313 901 319 1193 139 634 537 1053 263 1133 125 461 70 389 107 750 232 267 224 257 559 1280 256 390 72 120 169 1266 888 1019 212 415 107 206 289 1059 883 1358 779 1026 11 1212 70 940 776 1356 155 193 746 782 813 1215 340 405 1322 1340 525 1177 532 565 267 419 66 77 310 968 406 889 518 570 88 128 282 352 412 664 81 97 282 1329 6 7 113 1086 82 287 289 344 738 765 331 1354 778 814 351 587 465 939 310 327 1 249 1094 1305 834 891 215 410 526 966 476 993 8 26 87 225 156 1041 84…
Output: 28

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Galen's canals Longest Trail - MEDIUM Coding Problem | CodeTikki