CT42734

The Longest Trail of the Wayward roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the galleon yard of Masthead, Petr records each roads in a worn leather ledger. The guild wants answers, not guesses. 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 <= 1796; the input is a connected tree.

Example 1:

Input: 387 40 206 24 328 184 350 167 241 43 166 100 204 320 342 140 348 98 149 3 57 198 382 3 22 2 69 10 13 2 65 19 281 85 375 32 38 189 317 7 14 70 112 15 158 12 27 50 132 81 191 86 315 45 62 16 187 99 119 93 293 67 309 197 351 46 301 256 266 246 297 173 179 85 116 95 167 242 333 112 336 24 307 40 89 32 34 28 51 313 345 13 19 159 180 201 381 141 236 233 237 1 11 45 193 189 196 360 383 53 131 78 87 7 105 3 78 86 226 9 373 16 18 276 335 105 168 16 324 95 151 123 223 115 319 9 244 32 303 117 224 2 3 11 32 140 269 32 343 118 145 9 20 18 99 28 70 122 171 245 278 100 143 9 189 222 385 18 289 93 113 3 7 136 359 359 361 41 45 42 341 16 95 43 75 14 110 56 353 212 227 261 282 47 360 117 306 142 146 13 15 383 384 25 97 33 311 2 4 220 222 110 157 73 84 148 177 53 83 150 173 89 300 97 98 73 172 63 67 82 144 …
Output: 21

Example 2:

Input: 1399 487 747 147 485 716 1042 1262 1268 68 72 148 221 696 708 7 618 390 863 486 1321 230 839 39 52 273 633 412 847 365 496 193 1095 128 237 940 1311 845 1309 76 204 540 840 30 67 907 1248 253 1052 399 871 186 319 496 636 1129 1194 63 247 30 187 204 514 179 1141 322 727 111 1255 705 1015 46 388 772 818 50 464 908 960 1179 1325 399 561 46 91 130 877 275 439 168 174 44 718 426 824 828 923 179 914 71 302 9 36 392 1364 585 1223 447 1000 402 660 437 812 97 458 372 1191 725 924 236 756 573 1035 345 643 305 307 45 853 539 1008 331 409 9 250 447 649 257 445 571 767 706 993 18 58 62 114 455 487 361 398 1115 1333 227 1144 551 1175 130 436 426 1081 246 631 92 475 258 656 708 1069 118 154 477 1293 277 1195 121 608 819 995 194 825 36 391 876 1154 373 686 172 205 129 200 431 697 696 861 115 1232 3 6 714 …
Output: 26

Example 3:

Input: 1321 257 316 45 1003 52 537 822 1064 375 1128 236 711 2 77 1141 1257 44 52 435 816 374 651 673 1256 511 869 900 963 14 17 536 653 672 710 774 1284 66 73 583 717 220 967 15 253 516 847 225 824 5 71 70 423 952 1121 274 1101 120 265 105 477 142 296 409 1057 621 1168 843 1011 102 1287 781 785 230 469 160 520 848 855 594 951 114 143 437 1024 987 1006 227 449 704 859 661 839 277 1150 63 181 82 1188 14 612 136 721 222 254 66 633 117 1046 755 878 211 351 188 279 489 1139 464 635 768 1316 4 50 158 232 90 1090 214 1321 209 559 210 370 810 912 583 584 759 1007 721 994 64 867 86 406 397 1089 61 281 6 48 559 884 647 716 63 642 14 880 513 688 24 41 54 888 456 1161 300 956 40 652 775 1208 462 929 21 489 302 546 211 1092 133 212 160 692 183 446 407 1214 258 1118 49 104 17 671 1040 1149 7 206 608 903 548 6…
Output: 26

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Longest Trail of the Wayward roads - MEDIUM Coding Problem | CodeTikki