#5735. 「OOI 2026 Day1」萨沙的任务

标签: 传统 | 时间限制: 5000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2026 Day1 T3 「Задачи от Саши」 / 「Tasks from Sasha」。

萨沙最近搬进了一栋多层建筑。这栋建筑共有 $n$ 层，编号从 $1$ 到 $n$。每一层都恰好住着一名住户。楼层之间建有 $n-1$ 段楼梯，但这些楼梯不一定连接相邻的楼层。已知对于除第 $1$ 层以外的每一层，都恰好有一段楼梯通往更低的楼层。具体而言，对于第 $i$ 层 $(2 \leq i \leq n)$，这段楼梯通向第 $p_i$ 层。

萨沙准备解决 $k$ 个任务，编号从 $1$ 到 $k$。萨沙计算出，对于编号为 $i$ 的任务，在第 $x_i$ 层解决是最理想的。由于这些任务各不相同，所有的 $x_i$ 也互不相同。

独自一人解决任务非常枯燥，所以对于每个任务，萨沙都想邀请至少一名住户共同参与。然而，这栋楼的住户非常讨厌爬楼梯，他们只愿意走下楼梯前往任务所在的楼层。因此，只有在可以从第 $j$ 层出发、通过若干段（可能为零）向低楼层延伸的楼梯到达第 $x_i$ 层的情况下，萨沙才能邀请第 $j$ 层的住户来解决任务 $i$。换句话说，只有当满足 $j=x_i$、或 $p_j=x_i$、或 $p_{p_j}=x_i$ 等条件时，第 $j$ 层的住户才能参与任务 $i$。

住户们也非常讨厌多走不必要的下坡路。因此，如果萨沙邀请了一组人共同解决某个任务，只有在这些人都能到达的最高楼层，他们才愿意聚在一起解决该任务。例如，如果从第 $3$ 层有一段楼梯通向第 $2$ 层，萨沙将无法邀请第 $2$ 层和第 $3$ 层的住户在第 $1$ 层解决任务，因为他们完全可以在更高的第 $2$ 层聚集。

萨沙不想显得太爱打扰人，所以对于每一层的住户，萨沙最多只会邀请其参与一个任务。当然，萨沙也可以选择不邀请某些楼层的住户。

萨沙还有一个最喜欢的任务，除了你他不会告诉任何人。但为了让他告诉你这个任务，你需要帮他计算出有多少种不同的邀请方案，使得上述所有限制都能得到满足。如果至少有一个任务由不同的住户集合解决，则认为这两种方案是不同的。

输入格式

第一行包含两个整数 $n$ 和 $k$ $(3 \leq n \leq 10^6, 1 \leq k \leq \min(n, 2000))$，分别表示楼层数量和任务数量。

第二行包含 $k$ 个整数 $x_1, x_2, \dots, x_k$ $(1 \leq x_i \leq n)$，表示萨沙解决每个任务所在的楼层。保证所有的 $x_i$ 互不相同。

第三行包含 $n-1$ 个整数 $p_2, p_3, \dots, p_n$ $(1 \leq p_i < i)$，其中 $p_i$ 描述了从第 $i$ 层通向更低楼层的楼梯所连接的楼层编号。

输出格式

输出一个整数，即满足所有限制的邀请住户方案总数对 $998244353$ 取模后的结果。

样例 1

输入

3 1
1
1 1

输出

5

在第一个样例中，萨沙共有五种邀请住户的方式：

• 仅邀请第 $1$ 层的住户；
• 邀请第 $1$ 层和第 $2$ 层的住户；
• 邀请第 $1$ 层和第 $3$ 层的住户；
• 邀请第 $1$ 层、第 $2$ 层和第 $3$ 层的住户；
• 邀请第 $2$ 层和第 $3$ 层的住户。

萨沙不能只邀请第 $2$ 层的住户来解决任务，因为那样的话，所有想解决任务的住户能聚集的最高楼层将是第 $2$ 层，而萨沙希望在第 $1$ 层解决任务。

在第二个样例中，两种不同的合适邀请方案如下：

• 邀请第 $2$ 层和第 $6$ 层的住户解决第一个任务，邀请第 $5$ 层的住户解决第二个任务。
• 邀请第 $2$ 层的住户解决第一个任务，邀请第 $5$ 层和第 $6$ 层的住户解决第二个任务。

样例 2

输入

6 2
2 5
1 2 3 4 5

输出

12

样例 3

输入

7 3
2 7 1
1 1 2 2 3 3

输出

62

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。