← 返回题目列表

Codeforces · 1146/F

F. 叶分区

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

您将获得一棵有根树,其中包含 $$$n$$$ 节点,标记为从 $$$1$$$ 到 $$$n$$$。该树的根节点为$$$1$$$。第 $$$i$$$ 节点的父节点是 $$$p_i$$$。叶子是没有子节点的节点。对于给定的一组叶子 $$$L$$$,让 $$$f(L)$$$ 表示包含所有叶子 $$$L$$$ 的最小连通子图。

您希望对叶子进行分区,以便对于分区的任意两个不同集合 $$$x, y$$$,$$$f(x)$$$ 和 $$$f(y)$$$ 是不相交的。

计算叶分区的方式数量,以 $$$998244353$$$ 为模。如果有两个叶子,使得它们在一种方式中位于同一集合中,但在另一种方式中位于不同集合中,则两种方式是不同的。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 200\,000$$$) — 树中的节点数。

下一行包含 $$$n-1$$$ 整数 $$$p_2, p_3, \ldots, p_n$$$ ($$$1 \leq p_i < i$$$)。

输出

打印一个整数,即叶子分区的方式数,以 $$$998244353$$$ 为模。

示例

输入 #1

5
1 1 1 1

输出 #1

12

输入 #2

10
1 2 3 4 5 6 7 8 9

输出 #2

1

注意

在第一个示例中,叶节点是 $$$2,3,4,5$$$。叶子的划分方式如下图

在第二个示例中,唯一的叶子是节点 $$$10$$$,因此只有一个分区。请注意,节点 $$$1$$$ 不是叶子。