← 返回题目列表

AtCoder · arc150_d

D. 删除扭蛋

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

分数: 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