2070D.md (2466B)
1 Source: https://codeforces.com/problemset/problem/2070/D 2 3 D. Tree Jumps 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a rooted tree, consisting of $n$ vertices. The vertices in the tree are numbered from $1$ to $n$, and the root is the vertex $1$. Let $d_x$ be the distance (the number of edges on the shortest path) from the root to the vertex $x$. 22 23 There is a chip that is initially placed at the root. You can perform the following operation as many times as you want (possibly zero): 24 25 * move the chip from the current vertex $v$ to a vertex $u$ such that $d_u = d_v + 1$. If $v$ is the root, you can choose any vertex $u$ meeting this constraint; however, if $v$ is not the root, $u$ should not be a neighbor of $v$ (there should be no edge connecting $v$ and $u$). 26 27  28 29 For example, in the tree above, the following chip moves are possible: $1 \rightarrow 2$, $1 \rightarrow 5$, $2 \rightarrow 7$, $5 \rightarrow 3$, $5 \rightarrow 4$, $3 \rightarrow 6$, $7 \rightarrow 6$. 30 31 A sequence of vertices is valid if you can move the chip in such a way that it visits all vertices from the sequence (and only them), in the order they are given in the sequence. 32 33 Your task is to calculate the number of valid vertex sequences. Since the answer might be large, print it modulo $998244353$. 34 35 Input 36 37 The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 38 39 The first line of each test case contains a single integer $n$ ($2 \le n \le 3 \cdot 10^5$). 40 41 The second line contains $n-1$ integers $p_2, p_3, \dots, p_n$ ($1 \le p_i \lt i$), where $p_i$ is the parent of the $i$-th vertex in the tree. Vertex $1$ is the root. 42 43 Additional constraint on the input: the sum of $n$ over all test cases doesn't exceed $3 \cdot 10^5$. 44 45 Output 46 47 For each test case, print a single integer — the number of valid vertex sequences, taken modulo $998244353$. 48 49 Example 50 51 Input 52 53 ``` 54 3 55 56 4 57 58 1 2 1 59 60 3 61 62 1 2 63 64 7 65 66 1 2 2 1 4 5 67 ``` 68 69 Output 70 71 ``` 72 4 73 2 74 8 75 ``` 76 77 Note 78 79 In the first example, the following sequences are valid: $[1]$, $[1, 2]$, $[1, 4]$, $[1, 4, 3]$. 80 81 In the second example, the following sequences are valid: $[1]$, $[1, 2]$. 82 83 In the third example, the following sequences are valid: $[1]$, $[1, 2]$, $[1, 2, 7]$, $[1, 2, 7, 6]$, $[1, 5]$, $[1, 5, 3]$, $[1, 5, 3, 6]$, $[1, 5, 4]$.