P15448 [IOI 2011] Tropical Garden

**本题仅支持 C++ 语言提交。** 5s 256MB 更改了 in 和 out 文件格式以适配洛谷且防作弊 在洛谷评测不需要包含额外头文件，但需要在代码开头加入以下内容： ```cpp extern "C"{ void count_routes(int N, int M, int P, int R[][2], int Q, int G[]); void answer(int x); }

植物学家 Somhed 定期带领学生团体参观泰国最大的热带花园之一。这个花园的景观由 $N$ 个喷泉（编号为 $0, 1,\ldots, N-1$）和 $M$ 条小径组成。每条小径连接一对不同的喷泉，并且可以双向通行。每个喷泉至少有一条小径离开。这些小径沿途有 Somhed 想要欣赏的美丽植物收藏。每个团体可以从任意喷泉开始他们的行程。 Somhed 热爱美丽的热带植物。因此，从任何一个喷泉出发，他和他的学生们会走离开该喷泉的最美丽的小径，除非这条小径是刚刚走过的并且有另一条可选。在这种情况下，他们会改走第二美丽的小径。当然，如果没有可选的小径，他们会原路返回，第二次使用同一条小径。注意，由于 Somhed 是专业植物学家，对他来说没有两条小径是同样美丽的。 他的学生们对植物不太感兴趣。不过，他们非常想在位于编号为 $P$ 的喷泉旁的顶级餐厅吃午餐。Somhed 知道他的学生们会在恰好走了 $K$ 条小径后感到饥饿，$K$ 的值可能因学生团体而异。Somhed 想知道他可以为每个团体选择多少条不同的路线，给定以下条件： - 每个团体可以从任意喷泉出发； - 连续选择的小径必须按照上述方式； - 每个团体必须在恰好走了 $K$ 条小径后，在 $P$ 号喷泉结束。 注意，他们可以在路线中提前经过 $P$ 号喷泉，尽管他们仍然需要在 $P$ 号喷泉结束路线。 ### 交互细节 根据给出的喷泉和小径信息，你需要为 $Q$ 个学生团体找出答案；也就是说，为 $Q$ 个 $K$ 的值找出答案。 编写一个过程 `count_routes(N, M, P, R, Q, G)`，它接受以下参数： - $N$ - 喷泉的数量。喷泉编号为 $0$ 到 $N-1$。 - $M$ - 小径的数量。小径编号为 $0$ 到 $M-1$。小径将按美丽程度降序给出：对于 $0 \le i < M-1$，小径 $i$ 比小径 $i+1$ 更美丽。 - $P$ - 顶级餐厅所在的喷泉。 - $R$ - 一个表示小径的二维数组。对于 $0 \le i < M$，小径 $i$ 连接喷泉 $R[i][0]$ 和 $R[i][1]$。回想一下，每条小径连接一对不同的喷泉，并且没有两条小径连接同一对喷泉。 - $Q$ - 学生团体的数量。 - $G$ - 一个包含 $K$ 值的一维整数数组。对于 $0 \le i < Q$，$G[i]$ 是第 $i$ 个团体将要走的路径数量 $K$。 对于 $0 \le i < Q$，你的过程必须找出第 $i$ 个团体可能采取的、恰好有 $G[i]$ 条小径且能到达 $P$ 号喷泉的路线数量。对于每个团体 $i$，你的过程应该调用过程 `answer(X)` 来报告路线数量为 $X$。答案必须按团体的相同顺序给出。如果没有有效路线，你的过程必须调用 `answer(0)`。 ### 交互示例 #### 示例 1  考虑图 1 所示的情况，其中 $N=6, M=6, P=0, Q=1, G[0]=3$，并且 $R=$ ```plain 1 2 0 1 0 3 3 4 4 5 1 5 ``` 注意小径是按美丽程度递减列出的。也就是说，小径 $0$ 是最美丽的，小径 $1$ 是第二美丽的，依此类推。 只有两条可能的有效路线能恰好走 $3$ 条小径： $1\to2\to1\to0$，以及 $5\to4\to3\to0$。 第一条路线从喷泉 $1$ 开始。从这里出发的最美丽小径通向喷泉 $2$。在喷泉 $2$ 处，团体别无选择，必须沿同一条小径返回。回到喷泉 $1$ 后，团体现在将避免走小径 $0$，而是选择小径 $1$。这条小径确实将他们带到了 $P=0$ 号喷泉。 因此，该过程应该调用 `answer(2)`。 #### 示例 2  考虑图 2 所示的情况，其中 $N=5, M=5, P=2, Q=2, G[0]=3, G[1]=1$，并且 $R=$ ```plain 1 0 1 2 3 2 1 3 4 2 ``` 对于第一个团体，只有一条有效路线能在走 $3$ 条小径后到达喷泉 $2$：$1\to0\to1\to2$。 对于第二个团体，有两条有效路线能在走 $1$ 条小径后到达喷泉 $2$：$3\to2$ 和 $4\to2$。 因此，`count_routes` 的正确实现应该首先调用 `answer(1)` 来报告第一个团体的答案，然后调用 `answer(2)` 来报告第二个团体的答案。

示例评分器按以下格式读取输入： - 第 $1$ 行：$N$、$M$ 和 $P$。 - 第 $2$ 行到第 $M+1$ 行：小径的描述；即第 $i+2$ 行包含 $R[i][0]$ 和 $R[i][1]$，以空格分隔，其中 $0 \le i < M$。 - 第 $M+2$ 行：$Q$。 - 第 $M+3$ 行：数组 $G$，为一串空格分隔的整数序列。 - 第 $M+4$ 行：预期解的数组，为一串空格分隔的整数序列。

示例评分器输出：对于此任务，这些文件中的每一个都应精确地包含文本 Correct.

### 数据范围 - **子任务 1 (49 分)** - $2 \le N \le 1000$ - $1 \le M \le 10^4$ - $Q = 1$ - $G$ 的每个元素是介于 $1$ 和 $100$ 之间的整数（含端点）。 - **子任务 2 (20 分)** - $2 \le N \le 1.5\times10^5 $ - $1 \le M \le 1.5\times10^5 $ - $Q = 1$ - $G$ 的每个元素是介于 $1$ 和 $10^9$ 之间的整数（含端点）。 - **子任务 3 (31 分)** - $2 \le N \le 1.5\times10^5 $ - $1 \le M \le 1.5\times10^5 $ - $1 \le Q \le 2,000 $ - $G$ 的每个元素是介于 $1$ 和 $10^9$ 之间的整数（含端点）。