Tree Jumps ( Educational Codeforces Round 175 (Rated for Div. 2) )

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$.

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):

• 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$).

For example, in the tree above, the following chip moves are possible: $1\to 2$, $1\to 5$, $2\to 7$, $5\to 3$, $5\to 4$, $3\to 6$, $7\to 6$.

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.

Your task is to calculate the number of valid vertex sequences. Since the answer might be large, print it modulo $998244353$.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($2\le n\le 3\cdot 10^5$).

The second line contains $n-1$ integers $p_2,p_3,\dots ,p_n$ ($1\le p_i\le i$), where $p_i$ is the parent of the $i$-th vertex in the tree. Vertex $1$ is the root.

Additional constraint on the input: the sum of $n$ over all test cases doesn’t exceed $3\cdot 10^5$.

Output

For each test case, print a single integer — the number of valid vertex sequences, taken modulo $998244353$.

Example

input

3
4
1 2 1
3
1 2
7
1 2 2 1 4 5

output

4
2
8

Note

In the first example, the following sequences are valid: $[1]$, $[1,2]$, $[1,4]$, $[1,4,3]$.

In the second example, the following sequences are valid: $[1]$, $[1,2]$.

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]$.

题面描述

你有一个树，树中有 n 个节点，节点编号从 1 到 n，根节点是节点 1。定义 $d_x$ 为从根节点到节点 $x$ 的距离（即最短路径上的边数）。

有一个棋子最开始放在根节点。你可以执行以下操作若干次（可能为零次）：

• 将棋子从当前节点 $v$ 移动到一个距离为 $d_v+1$ 的节点 $u$。如果 $v$ 是根节点，则可以选择任何符合条件的节点；如果 $v$ 不是根节点，则 $u$ 必须不是 $v$ 的邻居（即树中没有边连接 $v$ 和 $u$）。

例如，在上面给出的树中，以下是有效的棋子移动：

• $1\to 2$, $1\to 5$
• $2\to 7$, $5\to 3$, $5\to 4$
• $3\to 6$, $7\to 6$

一段顶点序列是有效的，如果你能按给定的顺序移动棋子并访问所有的顶点，且只访问这些顶点。

你的任务是计算出有多少种有效的顶点序列。由于结果可能很大，请输出结果对 $998244353$ 取模后的值。

输入

• 第一行输入一个整数 $t$，表示测试用例的数量。
• 对于每个测试用例：
  • 第一行输入一个整数 $n$，表示树的节点数量。
  • 第二行输入 $n-1$ 个整数 $p_2,p_3,\dots ,p_n$，表示树中第 $i$ 个节点的父节点为 $p_i$（$1\le p_i\le i$）。树的根节点为节点 $1$。

输出

对于每个测试用例，输出一个整数，表示可能的有效顶点序列的数量，对 $998244353$ 取模。

示例

输入：

3
4
1 2 1
3
1 2
7
1 2 2 1 4 5

输出：

4
2
8

解释

• 第一个测试用例：
  树的结构为：

        1
       / \
      2   5
     /   / \
    3   4   7
          /
         6
  

  有效的顶点序列包括：[1]，[1, 2]，[1, 4]，[1, 4, 3]。共计 4 种有效序列。

• 第二个测试用例：
  树的结构为：

        1
       / \
      2   3
  

  有效的顶点序列包括：[1]，[1, 2]。共计 2 种有效序列。

• 第三个测试用例：
  树的结构为：

        1
       / \
      2   5
     /   / \
    3   4   7
          /
         6
  

  有效的顶点序列包括：[1]，[1, 2]，[1, 2, 7]，[1, 2, 7, 6]，[1, 5]，[1, 5, 3]，[1, 5, 3, 6]，[1, 5, 4]。共计 8 种有效序列。

---

题解

我们可以使用动态规划来解决这个问题。设 $d{p}_v$ 表示以顶点 $v$ 结尾的有效序列的数量。

为了计算 $d{p}_v$，我们可以遍历序列中所有之前的顶点 $u$，使得 $d_v=d_u+1$ 且 $u\ne p_v$（或者 $u$ 是根节点）。那么，$d{p}_v$ 就是所有满足条件的 $u$ 对应的 $d{p}_u$ 之和。

需要注意的是，顶点应该按照离根节点距离递增的顺序进行处理，因为否则，当我们在计算 $d{p}_v$ 中需要用到 $d{p}_u$ 时，$d{p}_u$ 可能还未被计算出来。然而，这种方法可能会非常慢，因为对于每个顶点 $v$，可能会有 $O(n)$ 个顶点 $u$。 为了加快这个解法的速度，我们可以观察到，如果顶点离根节点的距离相同，它们的 $dp$ 值的计算遵循相似的模式。

具体来说，我们只需要考虑树中前一“层”顶点的 $dp$ 值，同时排除它们的父节点。

因此，我们可以存储每一个“层”中所有 $dp$ 值的总和。设 $to{t}_i$ 是所有离根节点距离为 $i$ 的顶点 $v$ 对应的 $d{p}_v$ 之和。那么我们可以很容易地将 $d{p}_v$ 计算为 $to{t}_{d_v-1}-d{p}_{p_v}$（如果 $p_v$ 是根节点，则减去 $0$）。该问题的答案就是所有 $d{p}_v$ 值的总和。

为了根据顶点离根节点的距离对顶点进行排序，你可以使用深度优先搜索（DFS）（然后根据距离对顶点进行排序）或者广度优先搜索（BFS）。

或者你可以使用以下方法：由于对于每个顶点，其父节点的索引更小，我们可以按从 $1$ 到 $n$ 的顺序处理顶点，并设置 $d_v=d_{p_v}+1$。然后，对于每个深度，你可以构建一个包含该深度所有顶点的向量（将每个顶点添加到对应的向量中）。这种方法的时间复杂度为 $O(n)$。

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define BoBoowen ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
using namespace std;

const int mod = 998244353;

int n;

void solved()
{
    cin >> n;
    vector<int> g[n + 1];
    vector<int> dep(n + 1);
    vector<int> dp(n + 1);
    vector<int> tot(n + 1);
    
    // 构建树
    for (int i = 1; i < n; ++i)
    {
        int x;
        cin >> x;
        x--;
        g[x].push_back(i);
    }

    // 使用队列进行广度优先搜索，计算每个节点的dp值
    queue<int> q;
    q.push(0);  // 从根节点开始
    dp[0] = 1;  // 根节点的序列数为1
    
    while (!q.empty())
    {
        int now = q.front();
        q.pop();
        
        // 更新当前节点的序列数
        dp[now] = (dp[now] + tot[dep[now]]) % mod;
        
        // 更新该节点下一层的总和
        tot[dep[now] + 1] = (tot[dep[now] + 1] + dp[now]) % mod;
        
        // 继续处理所有子节点
        for (auto it : g[now])
        {
            dep[it] = dep[now] + 1;
            if (now != 0)
            {
                dp[it] = (mod - dp[now]) % mod;  // 确保非根节点的序列数的正确性
            }
            q.push(it);
        }
    }

    // 汇总结果
    int ans = 0;
    for (int i = 0; i <= n; ++i)
    {
        ans = (ans + dp[i]) % mod;
    }
    cout << ans << endl;
}

signed main()
{
    BoBoowen;

    int T = 1;
    cin >> T;
    while (T--)
    {
        solved();
    }
}

代码解析：

• 树的构建：通过 g 数组存储树的邻接表。每个节点的父节点通过输入构建。
• dp 数组：dp[i] 记录从根节点到节点 i 的有效序列数。初始化时，根节点的序列数为1。
• tot 数组：tot[i] 用来累加当前层次的有效序列数，以便在下一层的节点处理中使用。
• 广度优先搜索：通过队列进行广度优先搜索，逐层计算每个节点的有效序列数。
• 计算结果：最终通过累加所有节点的 dp 值得到最终结果。

时间复杂度：

• 对于每个测试用例，构建树的时间复杂度为 $O(n)$，广度优先搜索的时间复杂度也是 $O(n)$。因此，每个测试用例的时间复杂度为 $O(n)$，总的时间复杂度是 $O(T\times n)$，其中 $T$ 为测试用例的数量，$n$ 为每个测试用例中的节点数。由于题目约束条件，能够在时间限制内通过。

结论

通过构建树和使用动态规划，结合广度优先搜索的方式，可以高效地计算出每个测试用例的有效顶点序列数。