题目描述
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.
Input
The input is given from Standard Input in the following format:
N
$p_2 p_3 \dots p_{N}$
Output
Print the answer.
Constraints
- $2 \leq N \leq 2 \times 10^5$
- $1 \leq p_i < i$
- All values in the input are integers.
Sample Input 1
4
1 1 3
Sample 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}$.
Sample Input 2
15
1 2 1 1 4 5 3 3 5 10 3 6 3 13
Sample Output 2
515759610
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分