A - Tree Contraction Sequence Editorial /

Time Limit: 2 sec / Memory Limit: 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).