← 返回题目列表

Codeforces · 2070/D

D. 树跳

中文机器翻译题面 查看原题

给你一棵有根树,由 $$$n$$$ 个顶点组成。树中的顶点编号从$$$1$$$到$$$n$$$,根是顶点$$$1$$$。设 $$$d_x$$$ 为从根到顶点 $$$x$$$ 的距离(最短路径上的边数)。

有一个芯片最初放置在根部。您可以根据需要多次执行以下操作(可能为零):

  • 将筹码从当前顶点 $$$v$$$ 移动到顶点 $$$u$$$,使得 $$$d_u = d_v + 1$$$。如果$$$v$$$是根,则可以选择任何满足此约束的顶点$$$u$$$;但是,如果 $$$v$$$ 不是根,则 $$$u$$$ 不应该是 $$$v$$$ 的邻居(不应该有连接 $$$v$$$ 和 $$$u$$$ 的边)。

例如,在上面的树中,可以进行以下筹码移动:$$$1 \rightarrow 2$$$、$$$1 \rightarrow 5$$$、$$$2 \rightarrow 7$$$、$$$5 \rightarrow 3$$$、$$$5 \rightarrow 4$$$、$$$3 \rightarrow 6$$$、$$$7 \rightarrow 6$$$。

顶点序列是 有效 如果您可以按照序列中给出的顺序移动芯片,使其访问序列中的所有顶点(并且仅访问它们)。

您的任务是计算有效顶点序列的数量。由于答案可能很大,因此打印它对 $$$998244353$$$ 取模。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$)。

第二行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \lt i$$$),其中 $$$p_i$$$ 是树中第 $$$i$$$ 顶点的父顶点。顶点 $$$1$$$ 是根。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,打印一个整数 - 有效顶点序列的数量,以 $$$998244353$$$ 为模。

示例

输入
复制

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

输出
复制

4
2
8

注意

在第一个示例中,以下序列有效:$$$[1]$$$、$$$[1, 2]$$$、$$$[1, 4]$$$、$$$[1, 4, 3]$$$。

在第二个示例中,以下序列有效:$$$[1]$$$、$$$[1, 2]$$$。

在第三个示例中,以下序列有效: $$$[1]$$$、$$$[1, 2]$$$、$$$[1, 2, 7]$$$、$$$[1, 2, 7, 6]$$$、$$$[1, 5]$$$、$$$[1, 5, 3]$$$、$$$[1, 5, 3, 6]$$$, $$$[1, 5, 4]$$$。