CT39078

Qadir and the Longest Trail

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Qadir the measurer watches over the canyon post of Redrock's stores of tunnels. 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 <= 2470; the input is a connected tree.

Example 1:

Input: 1665 648 910 505 1033 126 221 617 1042 5 150 270 580 344 1650 10 18 84 1469 601 706 71 90 461 531 337 972 780 881 84 165 438 909 181 1142 60 916 103 120 182 780 850 1278 955 1475 138 1570 784 1309 5 113 430 1406 458 665 232 296 44 1037 923 1443 497 738 283 842 456 800 822 955 148 200 214 292 121 195 516 650 516 1534 367 1488 301 562 353 1031 1124 1223 790 1383 610 963 516 1024 89 483 240 1135 565 1063 85 146 145 1312 432 1357 66 451 760 1365 553 990 1322 1523 102 1398 672 748 501 992 148 630 516 907 836 1592 375 633 848 1200 1330 1442 57 116 56 327 201 271 73 256 852 941 1170 1596 637 831 1078 1579 402 882 521 1520 7 17 73 260 320 1264 31 92 728 1163 467 1040 666 694 66 1321 575 759 37 187 855 939 62 503 111 134 151 961 637 1225 270 686 138 602 161 1265 66 646 595 802 183 527 519 1662 157 …
Output: 24

Example 2:

Input: 174 63 72 97 129 129 165 75 80 20 34 81 142 52 99 87 132 6 12 9 10 3 6 21 30 17 33 80 83 134 159 14 26 1 5 84 123 2 28 61 87 117 127 108 130 32 68 13 15 31 90 18 21 1 3 62 79 63 118 85 138 108 119 142 144 49 57 12 14 88 169 34 55 13 94 16 62 18 92 38 163 12 110 18 75 8 45 111 141 108 154 4 157 4 67 38 96 101 161 13 114 34 50 61 81 155 156 50 120 1 166 94 106 36 56 82 97 70 95 55 70 76 168 18 23 79 160 89 126 23 25 18 155 3 43 67 125 19 53 37 88 85 102 66 103 34 51 25 27 22 105 88 135 137 164 51 158 4 29 34 64 101 146 19 93 9 16 37 128 41 113 38 59 1 2 3 143 5 39 75 152 61 100 43 150 79 91 9 63 110 140 73 162 29 98 40 124 11 13 7 9 3 148 76 111 37 172 71 173 97 149 117 134 106 116 3 22 97 121 38 54 93 151 21 41 67 74 50 52 35 131 69 76 35 60 51 147 145 174 143 145 134 136 8 32 70 112 31 42 …
Output: 17

Example 3:

Input: 928 745 785 19 76 151 736 71 91 229 784 32 143 255 871 35 61 99 493 86 499 69 87 248 675 2 855 630 727 53 146 472 490 506 553 271 505 97 370 293 732 186 363 6 49 600 620 104 108 316 474 48 498 866 915 259 577 407 457 346 602 35 109 349 738 560 867 149 605 66 514 137 236 268 626 490 622 31 163 193 312 112 135 104 179 537 538 286 368 63 358 26 694 18 213 432 574 452 789 303 737 40 66 77 734 191 393 261 282 217 308 415 743 25 611 12 110 563 755 73 228 150 259 8 13 88 96 107 189 131 153 21 56 5 191 495 525 310 322 729 872 146 510 516 921 52 181 59 273 388 435 75 81 326 841 1 17 107 842 119 444 438 472 251 253 39 686 62 246 422 480 60 128 4 14 293 295 61 103 37 679 21 23 18 45 110 178 120 617 121 317 692 852 107 241 11 93 464 746 62 247 796 803 351 705 328 439 50 99 567 885 562 692 64 95 177 31…
Output: 21

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Qadir and the Longest Trail - MEDIUM Coding Problem | CodeTikki