AT_arc150_d [ARC150D] Removing Gacha
题目描述
有一棵有 $N$ 个顶点的有根树,顶点编号为 $1$ 到 $N$。顶点 $1$ 是这棵树的根,对于每个顶点 $i\ (2\leq i)$,其父节点为 $p_i$。
每个顶点有白色和黑色两种颜色。初始时所有顶点都是白色。
在这棵有根树中,如果从根节点 $1$ 到顶点 $i$ 的唯一简单路径上的所有顶点(包括 $1$ 和 $i$)都是黑色,则称顶点 $i$ 为“好顶点”。否则称为“坏顶点”。
你需要重复进行如下操作,直到所有顶点都变为黑色为止:从所有“坏顶点”中等概率随机选取一个顶点,并将其涂成黑色。
请你求出将所有顶点都变为黑色所需操作次数的期望值,并对 $998244353$ 取模。
期望值 $\bmod\ 998244353$ 的定义:可以证明,所求的期望值一定是有理数,并且在本题的约束下,若将其表示为最简分数 $\frac{P}{Q}$,则 $Q\not\equiv 0\pmod{998244353}$。因此,存在唯一的整数 $R$ 满足 $R\times Q\equiv P\pmod{998244353},\ 0\leq R
输入格式
输入为以下格式,从标准输入读取。
> $N$ $p_2$ $p_3$ $\dots$ $p_{N}$
输出格式
请输出答案。
说明/提示
### 数据范围
- $2\leq N\leq 2\times 10^5$
- $1\leq p_i