2598. [IOI2011]garden
#2598. [IOI2011]garden
题目描述
植物学家 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)。
输入格式
.jpg)
.jpg)
输出格式
样例
样例输入
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