AtCoder Regular Contest 150
D
Removing Gacha
AtCoder
⌀ 2407
原题
← CE →
翻译中…

Problem Statement

翻译中…

We have a rooted tree with $N$ vertices numbered $1$ to $N$. Vertex $1$ is the root of the tree, and the parent of vertex $i\ (2\leq i)$ is vertex $p_i$.

翻译中…

Each vertex has a color: black or white. Initially, all vertices are white.

翻译中…

In this rooted tree, vertex $i$ is said to be good when all vertices on the simple path connecting vertices $1$ and $i$ (including vertices $1$ and $i$) are black, and bad otherwise.

翻译中…

Until all vertices are black, let us repeat the following operation: choose one vertex from the bad vertices uniformly at random, and repaint the chosen vertex black.

翻译中…

Find the expected value of the number of times we perform the operation, modulo $998244353$.

翻译中…

The definition of the expected value modulo $998244353$ It can be proved that the sought expected value is always a rational number. Additionally, when that value is represented as an irreducible fraction $\frac{P}{Q}$, it can also be proved that $Q \not \equiv 0 \pmod{998244353}$. Therefore, there is a unique integer $R$ such that $R \times Q \equiv P \pmod{998244353}$ and $0 \leq R < 998244353$. Find this $R$.

翻译中…

Constraints

翻译中…
  • $2 \leq N \leq 2 \times 10^5$
  • $1 \leq p_i < i$
  • All values in the input are integers.
翻译中…

Input

翻译中…

The input is given from Standard Input in the following format:

翻译中…

N
p_2 p_3 \dots p_{N}

翻译中…

Output

翻译中…

Print the answer.

翻译中…

样例

Input #1
4
1 1 3
Output #1
831870300
Consider a case where the first three operations have chosen vertices $1$, $2$, and $4$ in this order. Then, vertices $1$ and $2$ are good, but vertex $4$ is still bad since vertex $3$, an ancestor of vertex $4$, is white. Thus, the fourth operation will choose vertex $3$ or $4$ uniformly at random. The expected value of the number of times we perform the operation is $\displaystyle \frac{35}{6}$.
Input #2
15
1 2 1 1 4 5 3 3 5 10 3 6 3 13
Output #2
515759610
题目信息
题号
arc150_d
时间限制
2 s
内存限制
1024 MB

题面与样例版权归 AtCoder 及出题人所有;中文翻译由 AI 生成(CI 管线),如有出入请以原文为准。