植物学家 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)。