/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
頂点に 1 から N の番号がついた N 頂点の根付き木があります。頂点 1 はこの木の根であり、頂点 i\ (2\leq i) の親頂点は頂点 p_i です。
各頂点は白、黒の色を持っています。はじめすべて頂点の色は白です。
根付き木において、頂点 1,\ i を結ぶ唯一の単純パス上の頂点 (頂点 1,\ i 含む) の色がすべて黒であるとき、頂点 i を「よい頂点」といいます。また、「よい頂点」ではない頂点を「わるい頂点」といいます。
すべての頂点の色が黒になるまで「『わるい頂点』から一様ランダムに頂点を 1 つ選び、その頂点を黒色で上塗りする」という操作を行います。
操作を行う回数の期待値を \bmod\ 998244353 で求めてください。
期待値 \text{mod }{998244353} の定義
求める期待値は必ず有理数になることが証明できます。 また、この問題の制約のもとでは、その値を既約分数 \frac{P}{Q} で表した時、Q \not \equiv 0 \pmod{998244353} となることも証明できます。 よって、R \times Q \equiv P \pmod{998244353}, 0 \leq R < 998244353 を満たす整数 R が一意に定まります。 この 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,\ 3 回目の操作で順に頂点 1,\ 2,\ 4 が選ばれた場合を考えます。このとき、頂点 1,\ 2 は「よい頂点」ですが、頂点 4 は祖先である頂点 3 が白色であるため「わるい頂点」です。よって 4 回目の操作で頂点を選ぶ際は頂点 3,\ 4 の中から一様ランダムに選びます。
操作を行う回数の期待値は \displaystyle \frac{35}{6} になります。
入力例 2
15 1 2 1 1 4 5 3 3 5 10 3 6 3 13
出力例 2
515759610
Score : 700 points
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.
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