/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
頂点に 1 から N までの番号がついた N 頂点の根付き木 T が与えられます。頂点 1 が根で、頂点 i (2 \leq i \leq N) の親は p_i (p_i \lt i) です。
頂点に 1 から N までの番号がついた N 頂点の有向グラフ G のうち、次の条件を全て満たすものを 良いグラフ と呼びます。(ここで、頂点 u から頂点 v へ向かう辺を辺 u \to v と表します。)
- G に含まれる全ての頂点の出次数は 1 である。
- G は偶数長の閉路を持たない。
- 2 \leq i \leq N を満たす i 全てに対して、G は辺 i \to p_i を含まない。
良いグラフである G 全てに対する 2^{(G に含まれる閉路の個数)} の総和を 998244353 で割った余りを求めてください。
制約
- 2 \leq N \leq 10^5
- 1 \leq p_i \lt i
- 入力で与えられる値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N p_2 p_3 \dots p_N
出力
良いグラフである G 全てに対する 2^{(G に含まれる閉路の個数)} の総和を 998244353 で割った余りを出力せよ。
入力例 1
2 1
出力例 1
6
良いグラフとしてあり得るものは次の 2 個です。
- 辺 1 \to 1, 辺 2 \to 2 を辺集合に持つグラフ
- 辺 1 \to 2, 辺 2 \to 2 を辺集合に持つグラフ
グラフに含まれる閉路の個数はそれぞれ 2 個, 1 個です。よって答えは (2^2 + 2^1) \bmod{998244353} = 6 になります。
入力例 2
3 1 2
出力例 2
34
例えば 辺 1 \to 2, 辺 2 \to 3, 辺 3 \to 1 を辺集合に持つグラフは良いグラフで、このグラフに含まれる閉路の個数は 1 個です。
入力例 3
5 1 2 1 1
出力例 3
3104
入力例 4
20 1 2 2 2 5 3 5 1 7 9 4 6 4 12 8 2 5 16 6
出力例 4
784973196
総和を 998244353 で割った余りを求める点に注意してください。
Score : 1000 points
Problem Statement
You are given a rooted tree T with N vertices labeled from 1 to N. The root is the vertex 1, and the parent of vertex i (2 \leq i \leq N) is p_i (p_i \lt i).
Consider a directed graph G with N vertices labeled from 1 to N. We call G good if it satisfies all of the following conditions (here, let u \to v denote an edge from vertex u to vertex v):
- Every vertex in G has outdegree 1.
- G has no cycle of even length.
- For every i (2 \leq i \leq N), G does not contain the edge i \to p_i.
Find the sum, modulo 998244353, of 2^{(\text{number of cycles in }G)} over all good graphs G.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq p_i \lt i
- All values given 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 sum, modulo 998244353, of 2^{(\text{number of cycles in }G)} over all good graphs G.
Sample Input 1
2 1
Sample Output 1
6
Here are the two possible good graphs:
- The graph with edges 1 \to 1 and 2 \to 2.
- The graph with edges 1 \to 2 and 2 \to 2.
The number of cycles in these graphs are 2 and 1, respectively. Thus, the answer is (2^2 + 2^1) \bmod{998244353} = 6.
Sample Input 2
3 1 2
Sample Output 2
34
For example, the graph with edges 1 \to 2, 2 \to 3, and 3 \to 1 is a good graph, whose number of cycle is 1.
Sample Input 3
5 1 2 1 1
Sample Output 3
3104
Sample Input 4
20 1 2 2 2 5 3 5 1 7 9 4 6 4 12 8 2 5 16 6
Sample Output 4
784973196
Remember to find the sum modulo 998244353.