分数: 700 点
问题陈述
我们有一棵有根树 N 顶点编号 1 to N。顶点 1 是树的根,也是顶点的父级 i\ (2\leq i) 是顶点 p_i.
每个顶点都有一种颜色:黑色或白色。最初,所有顶点都是白色的。
在这棵有根树中,顶点 i 据说是 好 当简单路径上的所有顶点连接顶点时 1 和 i (包括顶点 1 和 i)是黑色的,并且 坏 否则。
直到所有顶点都变成黑色,让我们重复以下操作:从坏顶点中随机均匀地选择一个顶点,并将所选顶点重新绘制为黑色。
求我们执行该操作的次数的期望值,取模 998244353.
期望值取模的定义 998244353
可以证明,求的期望值始终是有理数。此外,当该值表示为不可约分数时 \frac{P}{Q},还可以证明 Q \not \equiv 0 \pmod{998244353}。因此,存在一个唯一的整数 R 这样 R \times Q \equiv P \pmod{998244353} 和 0 \leq R < 998244353。找到这个 R.
约束
- 2 \leq N \leq 2 \times 10^5
- 1 \leq p_i < i
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N
p_2 p_3 \dots p_{N}
输出
打印答案。
示例输入 1
4 1 1 3
示例输出 1
831870300
考虑前三个操作选择了顶点的情况 1, 2,和 4 按此顺序。然后,顶点 1 和 2 很好,但是顶点 4 仍然很糟糕,因为顶点 3,顶点的祖先 4,是白色的。因此,第四个操作将选择顶点 3 or 4 均匀随机。
我们执行操作的次数的期望值为 \displaystyle \frac{35}{6}.
示例输入 2
15 1 2 1 1 4 5 3 3 5 10 3 6 3 13
示例输出 2
515759610