CT43307

Forester and the Longest Trail

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the poppy fields of Scarlet Plain, Forester the cartographer keeps careful count of the bridges. Plan the festival budget, every figure matters. 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 <= 2852; the input is a connected tree.

Example 1:

Input: 1950 711 1034 64 388 101 902 41 108 1423 1509 306 1486 332 948 1111 1460 44 921 1030 1439 888 1578 92 1833 392 521 45 120 18 20 475 664 497 677 892 1950 7 41 331 1090 789 1614 390 1075 1551 1697 130 712 156 487 395 1031 173 427 129 905 397 912 328 1672 152 723 523 851 23 505 419 1272 306 347 45 138 37 977 375 1710 383 438 384 501 115 243 1022 1909 448 970 289 604 964 1205 376 617 7 25 1443 1720 34 112 140 385 1139 1494 142 186 441 647 1462 1637 303 328 145 341 9 24 105 422 598 1193 497 628 307 598 579 1848 47 572 721 1224 110 452 204 480 929 1351 2 11 634 952 140 1014 118 166 1357 1386 411 1420 491 1080 476 1135 646 1905 432 788 83 135 1248 1606 62 1291 19 139 1376 1382 96 1458 380 1743 1280 1946 69 1082 885 1493 982 1414 16 126 368 408 235 927 124 1619 10 742 544 827 1365 1893 35 803 102 …
Output: 31

Example 2:

Input: 1025 189 254 53 122 40 108 294 454 924 946 38 39 131 219 180 247 610 615 222 252 205 641 257 934 129 892 114 194 815 880 99 105 277 854 590 1018 413 496 403 522 138 270 219 402 338 361 528 795 152 782 125 315 111 924 3 443 385 786 278 952 54 611 241 292 87 241 7 399 85 326 95 666 1 7 115 157 110 868 210 629 365 386 745 991 235 544 10 38 432 500 527 601 68 166 487 574 291 397 82 156 5 41 812 889 668 978 104 457 662 925 487 734 453 589 351 568 122 130 349 667 90 687 461 530 121 244 228 791 735 1016 758 890 224 797 22 382 86 383 104 727 599 806 9 42 112 906 403 1017 143 206 104 483 868 878 23 107 49 96 71 812 254 274 19 384 276 508 409 631 612 867 10 19 317 681 54 83 765 913 314 430 141 323 72 783 69 699 460 515 256 846 2 64 825 1000 92 278 327 516 678 953 259 442 30 50 455 569 369 432 102 51…
Output: 23

Example 3:

Input: 398 185 211 299 363 273 348 81 176 92 111 72 260 24 193 325 356 100 214 18 210 40 109 216 259 11 26 16 24 1 68 199 226 77 82 2 8 193 274 45 77 34 255 188 272 11 177 231 382 37 352 41 317 88 128 6 9 6 98 35 276 2 83 172 386 38 342 111 188 17 339 10 11 18 20 138 196 54 58 145 155 202 323 188 235 167 245 156 288 133 203 101 325 24 89 47 149 198 204 25 146 297 354 174 186 37 66 183 358 34 62 4 12 14 44 101 160 177 279 314 373 126 293 324 333 316 364 51 133 20 56 61 306 102 178 60 73 51 137 79 92 206 231 6 299 84 150 25 47 22 30 196 256 25 162 35 207 21 222 126 318 9 23 2 6 234 283 188 349 172 330 26 365 69 116 64 334 160 229 4 148 12 49 8 42 185 201 201 243 139 142 180 383 14 254 14 346 258 282 22 93 213 290 1 247 108 134 5 40 123 180 22 37 262 388 74 174 166 172 264 326 146 294 68 238 64 221 …
Output: 20

Constraints:

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

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