P16365 [OOI 2026] Tasks from Sasha

Sasha 最近搬进了一栋多层建筑。这栋建筑共有 $n$ 层，楼层编号从 $1$ 到 $n$。每层恰好住着一位住户。楼层之间共有 $n - 1$ 座楼梯，这些楼梯并不一定建在相邻楼层之间。已知除了第一层之外，每层恰好有一座楼梯通向更低的一层。对于第 $i$ 层（$2 \le i \le n$），这座楼梯通向编号为 $p_i$ 的楼层。 Sasha 计划解决 $k$ 个任务，编号从 $1$ 到 $k$。对于编号为 $i$ 的任务，Sasha 计算得出在第 $x_i$ 层来完成它是最优的。由于这些任务互不相同，所有的 $x_i$ 值也两两不同。 独自解决任务是很枯燥的，因此对于每个任务，Sasha 想要邀请至少一位住户和他一起完成。然而，这栋楼的住户非常讨厌爬楼梯，他们只愿意向下走到他们要完成任务的楼层。因此，Sasha 可以从第 $j$ 层邀请住户来完成第 $i$ 个任务，当且仅当从第 $j$ 层出发，可以通过若干次（可能为零次）每次只能走向更低楼层的楼梯到达第 $x_i$ 层。换言之，来自第 $j$ 层的住户能够完成第 $i$ 个任务，当且仅当 $j = x_i$，或 $p_j = x_i$，或 $p_{p_j} = x_i$，以此类推。 住户们极度讨厌不必要地向下走。因此，如果 Sasha 邀请了某个特定的住户集合来完成一项任务，他们将只愿意在**他们所有人都能下到的最高的楼层**集合完成该任务。例如，如果存在一座从第 $3$ 层通向第 $2$ 层的楼梯，那么 Sasha 就不能邀请第 $2$ 层和第 $3$ 层的住户到第 $1$ 层完成任务，因为所有住户可以在更高的楼层集合。 Sasha 不希望显得过于打扰，因此他邀请每位住户完成的的任务数不会超过一个。同时，他也可以选择完全不邀请某些楼层的住户来解决任务。 Sasha 还有一个最喜欢的任务，他不会与除你之外的任何人分享。但为了让他告诉你这个任务，你需要帮他计算满足所有限制条件的不同邀请住户的方式数目。如果至少有一个任务是由不同的住户集合解决的，则认为两种方式不同。

第一行包含两个整数 $n$ 和 $k$（$3 \le n \le 10^6$，$1 \le k \le \min(n, 2000)$）—— 建筑的楼层数和任务数量。 第二行包含 $k$ 个整数 $x_1$, $x_2$, $\ldots$, $x_k$（$1 \le x_i \le n$）—— Sasha 将在哪些楼层解决任务。保证所有的 $x_i$ 两两不同。 第三行包含 $n-1$ 个整数 $p_2$, $p_3$, $\ldots$, $p_n$（$1 \le p_i < i$），其中 $p_i$ 描述了从第 $i$ 层向下的楼梯通向哪一层。

输出一个数 —— 邀请住户与 Sasha 一同解决任务的不同方式数目，对 $998\,244\,353$ 取模。

### 样例解释 在第一个样例中，Sasha 有五种邀请住户解决任务的方式： - 仅与第 $1$ 层的住户一起； - 与第 $1$ 层和第 $2$ 层的住户一起； - 与第 $1$ 层和第 $3$ 层的住户一起； - 与第 $1$ 层、第 $2$ 层和第 $3$ 层的住户一起； - 与第 $2$ 层和第 $3$ 层的住户一起。 Sasha 不能只邀请第 $2$ 层的住户来解决任务，因为那样的话所有愿意解决该任务的住户能够集合的最高楼层将是第 $2$ 层，而 Sasha 希望在第 $1$ 层解决任务。 在第二个样例中，两种不同的适合邀请住户解决任务的方式可以如下所示： - 邀请第 $2$ 层和第 $6$ 层的住户解决第一个任务，并邀请第 $5$ 层的住户解决第二个任务。 - 邀请第 $2$ 层的住户解决第一个任务，并邀请第 $5$ 层和第 $6$ 层的住户解决第二个任务。 ### 计分 本题的测试数据分为 9 组。每组仅在通过该组内全部测试以及此前某些组的全部测试后，才能获得分数。注意，某些组不要求通过样例测试。**离线测试**表示你提交的解答在该组上的测试结果将仅在比赛结束后公布。每组的最终得分等于你所有提交的解答中在该组测试上获得的最高分。 | 子任务编号 | 分数 | 额外限制 | < | 必过组别 | 备注 | | :---: | :---: | :---: | :---: | :---: | :---: | | | | $n$ | $k$ | | | | $0$ | $0$ | -- | -- | -- | 题面样例。 | | $1$ | $12$ | $n \le 10$ | $k \le 10$ | $0$ | | | $2$ | $13$ | $n \le 500$ | $k \le 500$ | $0, 1$ | | | $3$ | $9$ | -- | $k = 1$ | -- | | | $4$ | $10$ | -- | -- | -- | $p_i = i - 1$ | | $5$ | $13$ | -- | -- | $4$ | 每个楼层与其相连的更高楼层不超过两个 | | $6$ | $14$ | $n \le 200\,000$ | $k \le 500$ | $0$ -- $2$ | | | $7$ | $11$ | -- | $k \le 500$ | $0$ -- $3, 6$ | | | $8$ | $10$ | -- | $k \le 1000$ | $0$ -- $3, 6, 7$ | | | $9$ | $8$ | -- | -- | $0$ -- $8$ | **离线测试** | 翻译由 DeepSeek V4 Pro 完成