← 返回题目列表

AtCoder · pakencamp_2022_day2_f

F. 最远

中文机器翻译题面 查看原题

配点 : 600 点

問題文

Paken 先生正在解决以下问题。

N 给出一棵顶点树。在顶部 它的编号为 1, 2, \ldots, N 。

对于每个顶点,找到距该顶点最远的单个顶点。如果有多个,您可以询问任何一个。

Paken解决了这个问题, 关于 1 \leq i \leq N 的顶点 距 i 最远的顶点之一是顶点 我发现它是 A_i 。

然而,即使我已经解决了问题,原来的树 A 中的一些值不再已知。你是帕肯君的数字序列。 我想恢复 A 。

现在你有长度了 给出了 N 序列 使用 B 。这个数字序列仍然存在 表示有关 A 的信息。在这种情况下,长度满足以下所有条件。 考虑 N 序列 使用 A 。

  • B_i \neq -1 如果 A_i = B_i 是
  • 有一棵树, 对于 1 \leq i \leq N 关于上游。 i 最远的顶点之一是顶点 A_i 是

满足这些条件 请告诉 Paken 有多少个 A 。不过,帕肯君有可能错误地解决了这个问题,所以条件满足了。 A 可能不存在。

请注意,答案可能很大,因此请改为写答案。 除以 998244353 后求余数。

制約

  • 所有输入均为整数
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq B_i \leq N 或 至少 B_i = -1 (1 \leq i \leq N)

小課題

  1. (100 点) B_i \neq -1 (1 \leq i \leq N)
  2. (100 点) 1 \leq N \leq 20
  3. (100 点) 1 \leq N \leq 2000
  4. (300 点)无附加约束 打印第

入力

输入是按以下格式从标准输入给出的。

N
B_1 B_2 \ldots B_N

出力

满足条件 A 的数量是 除以 998244353 后的余数 1 行输出。


入力例 1

3
2 -1 -1

出力例 1

3

A=(2, 1, 1), (2, 1, 2), (2, 3, 2) 可以得到第 3 是可能的。

这个输入/输出示例是一个小任务。 2, 3, 4 约束。


入力例 2

8
-1 8 7 5 -1 1 2 3

出力例 2

47

此输入示例是一个小作业。 2, 3, 4 约束。


入力例 3

4
1 2 3 4

出力例 3

0

Paken先生似乎错误地解决了这个问题,但是这个输入示例满足了子任务的所有约束。 请针对