2025的第一个下午从打开洛谷开始

久莲是一个喜欢出题的女孩子。

在今年的 World Final 结束以后，久莲特别喜欢计算几何，于是她打算在 NOI 的考场上也出一个计算几何：这是一道只有题目名字和计算几何相关的题目。

首先，久莲给出了一棵 n (n≥2) 个节点的有根树 T，根节点编号为 1。定义叶子节点为除了根以外所有度数恰好为 1 的节点。下图是一个树 T 的例子，其中叶子节点集合为 {3,4,5}。

image.png

接着通过这棵树，久莲构造了一个序列 A：

从根节点开始深度优先遍历整棵树，遍历时按照编号从小到大的顺序来访问孩子，这样可以得到一个树 T 的 DFS 序。 接着按照在 DFS 序中的出现顺序从前往后，久莲把所有叶子节点排成一排得到了一个序列 A。 更进一步地，通过序列 A，久莲定义了两个叶子节点 u,v 的距离 d(u,v)：假设 u 在 A 中是第 i 个元素，v 是第 j 个元素，则 d(u,v)=min(∣i−j∣,∣A∣−∣i−j∣)。其中 ∣A∣ 为序列的长度，即 T 的叶子个数，i,j 指的是出现的位置，从 1 开始计数。

上面的例子中，序列 A 为 {4,5,3}，其中 d(3,5)=d(3,4)=d(4,5)=1，3,4,5 的出现位置分别为 3,1,2。

最后，久莲给出了一个参数 K，利用这棵有根树 T 和序列 A，我们可以构造一张 n 个点的无重边无自环的无向图 G：两个不同的点 u,v 之间有边当且仅当它们满足下列条件中的至少一个：

在树 T 中存在连接 u,v 的边。 在树 T 中 u,v 都是叶子节点且 d(u,v)≤K。 当 K=1 或 2 时，上面的例子得到的图 G 都如下图所示：

image.png

现在久莲想让你来计算一下 G 中不同的哈密尔顿回路数量有多少条，答案可能很大，请对 998244353 取模后输出。

下面是一些补充定义：

无重边无自环的无向图 G 的一条哈密尔顿回路 H 是 G 中边的一个子集，其中每一个点恰好有两条不同的相邻边在 H 中，且任意两个点都可以通过 H 中的边直接或间接到达。 无重边无自环的无向图 G 的两条哈密尔顿回路 H 1 ​ ,H 2 ​ 是不同的当且仅当存在一条边 e 使得 e 在 H 1 ​ 中且不在 H 2 ​ 中。 输入描述

第一行输入两个整数 n,K，表示树 T 的点数以及久莲选定的参数 K。

第二行输入 n−1 个整数 f i ​ (1≤f i ​ ≤i)，其中 f i ​ 表示树 T 上存在边 (f i ​ ,i+1)。

输出描述

输出一行一个整数，表示哈密尔顿回路数量对 998244353 取模后的结果。

样例输入 1

5 1 1 1 2 2 样例输出 1

2 提示

数据范围与提示 样例解释 该样例和题面中的例子完全相同。两条哈密尔顿回路经过节点的顺序分别为 (1,2,4,5,3) 和 (1,2,5,4,3)。

子任务 编号 n K 特殊性质 编号 n K 特殊性质

1 ≤5 ≤3 无 . 11 ≤1000 ≤2 A

2 ≤10 ≤3 无 . 12 ≤1000 ≤2 A

3 ≤15 ≤3 无 . 13 ≤1000 ≤2 A

4 ≤20 ≤3 无 . 14 ≤1000 ≤2 无

5 ≤1000 =1 A . 15 ≤1000 ≤2 无

6 ≤1000 =1 A . 16 ≤1000 ≤2 无

7 ≤1000 =1 A . 17 ≤1000 ≤3 A

8 ≤1000 =1 无 . 18 ≤1000 ≤3 A

9 ≤1000 =1 无 . 19 ≤1000 ≤3 无

10 ≤1000 =1 无 . 20 ≤1000 ≤3 无

其中性质 A 为保证树上所有节点至多有两个孩子。

对于所有的数据，保证 1≤f i ​ ≤i，2≤n≤1000。

C++ 最近 上传 1