CT56739

The Cinderline Longest Trail

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the railway depot of Cinderline opens only for a perfect tally of roads. Lothar 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 <= 1501; the input is a connected tree.

Example 1:

Input: 234 74 111 148 218 22 57 1 76 121 179 22 34 29 147 51 205 6 15 54 58 11 189 2 5 144 165 7 129 114 118 10 44 58 62 15 17 55 184 70 231 7 80 1 13 182 201 19 32 36 224 117 144 38 105 3 9 66 204 51 83 206 211 181 199 46 61 183 195 12 46 199 212 75 104 213 228 196 220 21 140 128 193 72 84 23 127 20 23 98 166 7 51 78 135 11 35 20 42 172 230 50 52 22 28 81 95 18 79 61 73 11 20 85 217 2 12 68 75 137 146 15 126 61 99 13 18 103 115 70 186 162 234 38 66 62 181 72 125 51 122 16 142 122 180 3 102 1 2 23 175 114 117 147 188 61 86 35 39 3 54 122 176 44 59 89 190 64 161 19 53 115 153 156 164 103 156 3 106 108 132 59 215 54 109 68 168 105 108 10 172 102 159 13 29 170 208 72 82 63 169 54 87 80 157 73 114 16 31 115 121 114 171 35 112 29 130 45 209 41 88 114 133 74 110 103 182 66 96 15 27 25 85 36 160 80 170 …
Output: 18

Example 2:

Input: 1262 243 325 142 733 104 176 54 218 11 64 1112 1254 874 1121 77 957 599 719 858 910 152 229 567 1259 247 539 735 1164 1180 1240 78 1085 167 549 522 1200 62 1149 407 500 42 144 408 944 384 599 748 1100 320 536 238 431 83 587 504 1029 111 263 320 1044 1097 1130 38 47 187 654 465 894 70 550 38 53 472 795 87 127 460 1138 151 452 608 879 229 447 87 1011 308 842 306 1188 179 696 57 834 93 949 7 22 800 1197 702 1025 636 942 47 49 1010 1080 37 60 531 1052 396 823 238 465 19 746 607 960 559 1104 10 26 21 118 64 191 395 612 336 454 203 907 738 877 404 1226 798 1261 62 737 314 364 467 735 121 194 834 1168 276 434 519 534 146 206 385 1170 110 432 409 594 37 74 478 521 597 632 263 638 123 212 69 164 298 653 1167 1242 145 702 680 899 295 313 314 667 484 1144 72 274 15 31 482 661 157 471 150 196 545 760 …
Output: 29

Example 3:

Input: 145 65 73 1 2 39 119 22 81 19 21 25 29 34 144 1 19 10 46 39 42 60 63 9 84 29 105 36 101 11 34 8 9 37 66 58 90 24 30 30 33 23 55 65 97 70 121 11 25 93 115 94 99 90 93 11 41 34 38 8 143 18 91 62 77 19 49 37 48 68 79 6 15 29 44 4 11 112 117 19 103 40 127 32 128 69 138 3 122 113 120 66 106 14 110 3 142 116 140 8 18 10 24 21 37 77 112 55 131 12 61 64 124 4 113 32 47 73 134 37 109 25 27 49 92 28 71 10 31 19 28 8 54 29 107 24 39 62 96 30 102 6 133 82 87 122 129 85 88 88 114 2 8 3 53 10 35 2 3 48 52 10 16 59 60 72 80 87 116 90 98 135 139 17 26 23 130 43 76 122 136 67 100 41 137 15 17 19 57 6 22 3 20 2 64 1 5 61 82 97 145 35 43 107 123 20 32 12 118 53 59 14 135 12 68 41 141 59 95 16 23 40 85 18 36 3 7 28 50 56 94 6 14 8 45 48 58 5 10 47 74 13 78 40 83 116 125 48 56 23 104 53 69 1 67 56 86 8 12 55 1…
Output: 16

Constraints:

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

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