/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 700 点
問題文
N 頂点からなる根付き木があります． 頂点には 1,2,\ldots,N の番号がついており，根は頂点 1 です． 各頂点 v (2 \leq v \leq N) の親は頂点 P_v であり，1 \leq P_v < v を満たします．
また，各頂点は整数列を持っています． 最初，頂点 v の持つ列は (v) です．
これから次の操作を N-1 回行います．
- 2 \leq v \leq N を満たす頂点のうち，これまでの操作で選んでいない頂点 v を選び，現在の木におけるその親を u とする．
- 頂点 u の列の末尾に，頂点 v の列を連結する．
- 頂点 v をその親 u に縮約する．すなわち，頂点 v を削除し，その子をすべて頂点 u の子にする．
すべての操作を終えたとき，残った頂点 1 の列が (1,2,\ldots,N) と一致する操作列の個数を，998244353 で割った余りを求めてください．ここで，各回で選ぶ頂点の列が異なる操作列は異なるものとして数えます．
1 つの入力につき，T ケースを解いてください．
制約
- 1 \leq T \leq 125000
- 2 \leq N \leq 250000
- 1 \leq P_v < v (2 \leq v \leq N)
- T ケースにわたる N の総和は 250000 以下である．
- 入力される数値はすべて整数である．
入力
入力は標準入力から以下の形式で与えられる．
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる．
N P_2 P_3 \ldots P_N
出力
各テストケースについて，答えを出力せよ．
入力例 1
6 4 1 2 1 5 1 1 3 3 2 1 5 1 2 3 4 4 1 1 1 8 1 1 2 4 2 6 3
出力例 1
2 6 1 24 1 24
1 番目のテストケースでは，例えば頂点を 3,2,4 の順に選ぶと，次のように列が変化します．
- 頂点 3 を選ぶと，頂点 2 の列は (2,3) になる．
- 頂点 2 を選ぶと，頂点 1 の列は (1,2,3) になる．
- 頂点 4 を選ぶと，頂点 1 の列は (1,2,3,4) になる．
条件を満たす頂点の選択順は (2,3,4) と (3,2,4) の 2 通りです．
Score : 700 points
Problem Statement
There is a rooted tree with N vertices. The vertices are numbered 1,2,\ldots,N, and the root is vertex 1. The parent of each vertex v (2 \leq v \leq N) is vertex P_v, where 1 \leq P_v < v.
Additionally, each vertex holds an integer sequence. Initially, the sequence held by vertex v is (v).
You will perform the following operation N-1 times.
- Choose a vertex v with 2 \leq v \leq N that has not been chosen in any previous operation, and let u be its parent in the current tree.
- Concatenate the sequence of vertex v to the end of the sequence of vertex u.
- Contract vertex v into its parent u. That is, delete vertex v and make all of its children into children of vertex u.
Find the number, modulo 998244353, of operation sequences such that the sequence of the remaining vertex 1 after all operations equals (1,2,\ldots,N). Here, two operation sequences are considered different if their sequences of chosen vertices are different.
You are given T test cases; solve each of them.
Constraints
- 1 \leq T \leq 125000
- 2 \leq N \leq 250000
- 1 \leq P_v < v (2 \leq v \leq N)
- The sum of N over all test cases in a single input is at most 250000.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N P_2 P_3 \ldots P_N
Output
For each test case, output the answer.
Sample Input 1
6 4 1 2 1 5 1 1 3 3 2 1 5 1 2 3 4 4 1 1 1 8 1 1 2 4 2 6 3
Sample Output 1
2 6 1 24 1 24
In the first test case, if the vertices are chosen in the order 3,2,4, for example, the sequences change as follows.
- Choosing vertex 3 makes the sequence of vertex 2 equal to (2,3).
- Choosing vertex 2 makes the sequence of vertex 1 equal to (1,2,3).
- Choosing vertex 4 makes the sequence of vertex 1 equal to (1,2,3,4).
There are 2 orders of choosing vertices that satisfy the condition: (2,3,4) and (3,2,4).