[IOI2011]garden
时间限制：10s 空间限制：128MB
题目描述
植物学家 Somhed 带着几组学生去泰国最大的热带花园游玩。这个花园中有 N 个喷泉（编号为0, 1, …, N-1）和 M 条小路。每条小路连接一对不同的喷泉，两个喷泉间最多只有一条小路，小路是可以双向行走的。从任意一个喷泉出发至少有一条小路。每条小路的美丽程度决定了Somhed 选择走该条小路的优先程度。每组学生可以从任何一个喷泉出发。 在任何一个喷泉，Somhed 和他的学生们会选择最美丽的一条小路离开该喷泉，除非最美丽的这条小路是他们刚刚走过的，且还有其它小路可走。在这种情况下，他们会选择第二美丽的小路离开该喷泉。当然，如果没有第二美丽的小路可选，他们会选择刚刚走过的小路
再走回去。注意，对于Somhed 来说没有两条小路是同样美丽的。
Somhed 的学生们对小路的美丽与否不感兴趣，他们喜欢在喷泉 P 旁边的豪华餐厅吃午饭。Somhed 知道他的学生在走过恰好 K 条小路后会感觉饥饿，当然，对于不同组的学生K 可以不同。Somhed 想知道在下列条件下，对于每组学生有多少条不同的路径可选。
每组可以从任意喷泉出发；
但是接下来的路径必须按照上面描述的规则进行选择；
每组必须在恰好走过 K 条小路后到达喷泉 P 。
注意：他们在最终到达喷泉P之前可能曾经到过喷泉 P。
给定喷泉和小路的信息，以及 Q 个不同的 K，你要回答对于每个 K 来说, 有多少条不同的
路径可供候选。
写一个函数count_routes(N,M,P,R,Q,G)，该函数的参数如下：
N – 喷泉的数目。喷泉从 0 到 N-1 编号。
M – 小路的数目。小路从 0 到 M-1编号。所有小路按照其美丽程度从大到小的
顺序给出，即对于 0 ≤ i < M-1, 小路 i 比小路 i+1 更美丽。
P – 豪华餐厅所在的喷泉编号。
R – 描述小路的二维数组。对于 0 ≤ i < M, 小路 i 连接喷泉 R[i][0] 和喷泉
R[i][1]。 再次提醒：每条小路连接两个不同的喷泉，两个喷泉间最多只有一条小
路。
Q – 学生的组数。
G – 一个一维的整数数组，包含 Q 个不同的 K。对于 0 ≤ i < Q，G[i]表示第i 组
学生对应的K，即第 i 组学生经过K 条小路后要到达喷泉P。
对于 0 ≤ i < Q，你的函数必须给出可能的路径数目，满足第i 组学生在到达喷泉 P 时恰好
走过 G[i]条小路。对于第 i 组学生，你的函数必须调用函数 answer(X) 来给出可能的路径的
数目 X。答案给出的顺序必须和问题给出的顺序相同。如果没有合适的路径，你的函数应该
调用 answer(0)。
输入格式
输出格式
样例输入
780 780 0 1 0 0 2 2 3 3 1 4 1 5 4 6 5 7 6 8 7 9 8 10 9 11 10 12 11 13 12 14 13 15 14 16 15 17 16 18 17 19 18 20 19 21 20 22 21 23 22 24 23 25 24 26 25 27 26 28 27 29 28 30 29 31 30 32 31 33 32 34 33 35 34 36 35 37 36 38 37 39 38 40 39 41 40 42 41 43 42 44 43 45 44 46 45 47 46 48 47 49 48 50 49 51 50 52 51 53 52 54 53 55 54 56 55 57 56 58 57 59 58 60 59 61 60 62 61 63 62 64 63 65 64 66 65 67 66 68 67 69 68 70 69 71 70 72 71 73 72 74 73 75 74 76 75 77 76 78 77 79 78 80 79 81 80 82 81 83 82 84 83 85 84 86 85 87 86 88 87 89 88 90 89 91 90 92 91 93 92 94 93 95 94 96 95 97 96 98 97 99 98 100 99 101 100 102 101 103 102 104 103 105 104 106 105 107 106 108 107 109 108 110 109 111 110 112 111 113 112 114 113 115 114 116 115 117 116 118 117 119 118 120 119 121 120 122 121 123 122 124 123 125 124 126 125 127 126 128 127 129 128 130 129 131 130 132 131 133 132 134 133 135 134 136 135 137 136 138 137 139 138 140 139 141 140 142 141 143 142 144 143 145 144 146 145 147 146 148 147 149 148 150 149 151 150 152 151 153 152 154 153 155 154 156 155 157 156 158 157 159 158 160 159 161 160 162 161 163 162 164 163 165 164 166 165 167 166 168 167 169 168 170 169 171 170 172 171 173 172 174 173 175 174 176 175 177 176 178 177 179 178 180 179 181 180 182 181 183 182 184 183 185 184 186 185 187 186 188 187 189 188 190 189 191 190 192 191 193 192 194 193 195 194 196 195 197 196 198 197 199 198 200 199 201 200 202 201 203 202 204 203 205 204 206 205 207 206 208 207 209 208 210 209 211 210 212 211 213 212 214 213 215 214 216 215 217 216 218 217 219 218 220 219 221 220 222 221 223 222 224 223 225 224 226 225 227 226 228 227 229 228 230 229 231 230 232 231 233 232 234 233 235 234 236 235 237 236 238 237 239 238 240 239 241 240 242 241 243 242 244 243 245 244 246 245 247 246 248 247 249 248 250 249 251 250 252 251 253 252 254 253 255 254 256 255 257 256 258 257 259 258 260 259 261 260 262 261 263 262 264 263 265 264 266 265 267 266 268 267 269 268 270 269 271 270 272 271 273 272 274 273 275 274 276 275 277 276 278 277 279 278 280 279 281 280 282 281 283 282 284 283 285 284 286 285 287 286 288 287 289 288 290 289 291 290 292 291 293 292 294 293 295 294 296 295 297 296 298 297 299 298 300 299 301 300 302 301 303 302 304 303 305 304 306 305 307 306 308 307 309 308 310 309 311 310 312 311 313 312 314 313 315 314 316 315 317 316 318 317 319 318 320 319 321 320 322 321 323 322 324 323 325 324 326 325 327 326 328 327 329 328 330 329 331 330 332 331 333 332 334 333 335 334 336 335 337 336 338 337 339 338 340 339 341 340 342 341 343 342 344 343 345 344 346 345 347 346 348 347 349 348 350 349 351 350 352 351 353 352 354 353 355 354 356 355 357 356 358 357 359 358 360 359 361 360 362 361 363 362 364 363 365 364 366 365 367 366 368 367 369 368 370 369 371 370 372 371 373 372 374 373 375 374 376 375 377 376 378 377 379 378 380 379 381 380 382 381 383 382 384 383 385 384 386 385 387 386 388 387 389 388 390 389 391 390 392 391 393 392 394 393 395 394 396 395 397 396 398 397 399 398 400 399 401 400 402 401 403 402 404 403 405 404 406 405 407 406 408 407 409 408 410 409 411 410 412 411 413 412 414 413 415 414 416 415 417 416 418 417 419 418 420 419 421 420 422 421 423 422 424 423 425 424 426 425 427 426 428 427 429 428 430 429 431 430 432 431 433 432 434 433 435 434 436 435 437 436 438 437 439 438 440 439 441 440 442 441 443 442 444 443 445 444 446 445 447 446 448 447 449 448 450 449 451 450 452 451 453 452 454 453 455 454 456 455 457 456 458 457 459 458 460 459 461 460 462 461 463 462 464 463 465 464 466 465 467 466 468 467 469 468 470 469 471 470 472 471 473 472 474 473 475 474 476 475 477 476 478 477 479 478 480 479 481 480 482 481 483 482 484 483 485 484 486 485 487 486 488 487 489 488 490 489 491 490 492 491 493 492 494 493 495 494 496 495 497 496 498 497 499 498 500 499 501 500 502 501 503 502 504 503 505 504 506 505 507 506 508 507 509 508 510 509 511 510 512 511 513 512 514 513 515 514 516 515 517 516 518 517 519 518 520 519 521 520 522 521 523 522 524 523 525 524 526 525 527 526 528 527 529 528 530 529 531 530 532 531 533 532 534 533 535 534 536 535 537 536 538 537 539 538 540 539 541 540 542 541 543 542 544 543 545 544 546 545 547 546 548 547 549 548 550 549 551 550 552 551 553 552 554 553 555 554 556 555 557 556 558 557 559 558 560 559 561 560 562 561 563 562 564 563 565 564 566 565 567 566 568 567 569 568 570 569 571 570 572 571 573 572 574 573 575 574 576 575 577 576 578 577 579 578 580 579 581 580 582 581 583 582 584 583 585 584 586 585 587 586 588 587 589 588 590 589 591 590 592 591 593 592 594 593 595 594 596 595 597 596 598 597 599 598 600 599 601 600 602 601 603 602 604 603 605 604 606 605 607 606 608 607 609 608 610 609 611 610 612 611 613 612 614 613 615 614 616 615 617 616 618 617 619 618 620 619 621 620 622 621 623 622 624 623 625 624 626 625 627 626 628 627 629 628 630 629 631 630 632 631 633 632 634 633 635 634 636 635 637 636 638 637 639 638 640 639 641 640 642 641 643 642 644 643 645 644 646 645 647 646 648 647 649 648 650 649 651 650 652 651 653 652 654 653 655 654 656 655 657 656 658 657 659 658 660 659 661 660 662 661 663 662 664 663 665 664 666 665 667 666 668 667 669 668 670 669 671 670 672 671 673 672 674 673 675 674 676 675 677 676 678 677 679 678 680 679 681 680 682 681 683 682 684 683 685 684 686 685 687 686 688 687 689 688 690 689 691 690 692 691 693 692 694 693 695 694 696 695 697 696 698 697 699 698 700 699 701 700 702 701 703 702 704 703 705 704 706 705 707 706 708 707 709 708 710 709 711 710 712 711 713 712 714 713 715 714 716 715 717 716 718 717 719 718 720 719 721 720 722 721 723 722 724 723 725 724 726 725 727 726 728 727 729 728 730 729 731 730 732 731 733 732 734 733 735 734 736 735 737 736 738 737 739 738 740 739 741 740 742 741 743 742 744 743 745 744 746 745 747 746 748 747 749 748 750 749 751 750 752 751 753 752 754 753 755 754 756 755 757 756 758 757 759 758 760 759 761 760 762 761 763 762 764 763 765 764 766 765 767 766 768 767 769 768 770 769 771 770 772 771 773 772 774 773 775 774 776 775 777 776 778 777 779 778 1 96
样例输出
25
提示
没有写明提示
题目来源
没有写明来源