#P4776. [NOI2018] 多边形

[NOI2018] 多边形

题目描述

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

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

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

接着通过这棵树,久莲构造了一个序列 AA

  • 从根节点开始深度优先遍历整棵树,遍历时按照编号从小到大的顺序来访问孩子,这样可以得到一个树 TT 的 DFS 序。
  • 接着按照在 DFS 序中的出现顺序从前往后,久莲把所有叶子节点排成一排得到了一个序列 AA

更进一步地,通过序列 AA,久莲定义了两个叶子节点 u,vu, v 的距离 d(u,v)d(u, v):假设 uuAA 中是第 ii 个元素,vv 是第 jj 个元素,则 d(u,v)=min(ij,Aij)d(u, v) = \min(|i − j|, |A| − |i − j|)。其中 A|A| 为序列的长度,即 TT 的叶子个数,i,ji, j 指的是出现的位置,从 11 开始计数。

上面的例子中,序列 AA{4,5,3}\{4, 5, 3\},其中 d(3,5)=d(3,4)=d(4,5)=1d(3, 5) = d(3, 4) = d(4, 5) = 13,4,53, 4, 5 的出现位置分别为 3,1,23, 1, 2

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

  • 在树 TT 中存在连接 u,vu, v 的边。
  • 在树 TTu,vu, v 都是叶子节点且 d(u,v)Kd(u, v) \le K

K=1K = 122 时,上面的例子得到的图 GG 都如下图所示:

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

下面是一些补充定义:

  • 无重边无自环的无向图 GG 的一条哈密尔顿回路 HHGG 中边的一个子集,其中每一个点恰好有两条不同的相邻边在 HH 中,且任意两个点都可以通过 HH 中的边直接或间接到达。
  • 无重边无自环的无向图 GG 的两条哈密尔顿回路 H1,H2H_1, H_2 是不同的当且仅当存在一条边 ee 使得 eeH1H_1 中且不在 H2H_2 中。

输入格式

从文件 polygon.in 中读入数据。

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

第二行输入 n1n - 1 个整数 fi (1fii)f_i\ (1 \le f_i \le i),其中 fif_i 表示树 TT 上存在边 (fi,i+1)( f_i, i + 1)

输出格式

输出到文件 polygon.out 中。

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

5 1
1 1 2 2
2

提示

样例解释

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

子任务

编号 nn KK 特殊性质 编号 nn KK 特殊性质
11 5\le 5 3\le 3 . 1111 1000\le 1000 2\le 2 A
22 10\le 10 1212
33 15\le 15 1313
44 20\le 20 1414
55 1000\le 1000 =1=1 A 1515
66 1616
77 1717 3\le 3 A
88 1818
99 1919
1010 2020

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

对于所有的数据,保证 1fii1 \leq f_i \leq i2n10002 \leq n \leq 1000