← 返回题目列表

AtCoder · agc070_b

B. 奇怪的那森

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

分数: 1000 点

问题陈述

你得到了一棵有根的树 T 与 N 顶点标记自 1 to N。根就是顶点 1,以及顶点的父级 i (2 \leq i \leq N) is p_i (p_i \lt i).

考虑一个有向图 G 与 N 顶点标记自 1 to N。我们打电话 G 好 如果满足以下所有条件(这里,令 u \to v 表示从顶点开始的边 u 到顶点 v):

  • 中的每个顶点 G 具有出度 1.
  • G 没有偶数长度的循环。
  • 对于每个 i (2 \leq i \leq N), G 不包含边缘 i \to p_i.

求总和,模 998244353,属于 2^{(\text{number of cycles in }G)} 总体来说不错的图表 G.

约束

  • 2 \leq N \leq 10^5
  • 1 \leq p_i \lt i
  • 输入中给出的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N
p_2 p_3 \dots p_N

输出

打印总和,模数 998244353,属于 2^{(\text{number of cycles in }G)} 总体来说不错的图表 G.


示例输入 1

2
1

示例输出 1

6

这是两个可能的好图:

  • 有边的图 1 \to 1 和 2 \to 2.
  • 有边的图 1 \to 2 和 2 \to 2.

这些图中的周期数是 分别为 2 和 1。因此,答案是 (2^2 + 2^1) \bmod{998244353} = 6.


示例输入 2

3
1 2

示例输出 2

34

例如,有边的图 1 \to 2, 2 \to 3,和 3 \to 1 是一个很好的图,其循环次数为 1.


示例输入 3

5
1 2 1 1

示例输出 3

3104

示例输入 4

20
1 2 2 2 5 3 5 1 7 9 4 6 4 12 8 2 5 16 6

示例输出 4

784973196

记得求模求和 998244353.