【NOI2018】多边形 排行榜


时间限制: 10 s
空间限制: 512 MB

题目描述

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

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

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

接着通过这棵树,久莲构造了一个序列 $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$ 之间有边当且仅当它们满足下列条件中的至少一个:

当 $K = 1$ 或 $2$ 时,上面的例子得到的图 $G$ 都如下图所示:

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

下面是一些补充定义:

输入格式

从标准输入读入数据。

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

第二行输入 $n-1$ 个整数 $f_i(1 \leq f_i \leq i)$,其中 $f_i$ 表示树 $T$ 上存在边 $(f_i,i+1)$。

输出格式

输出到标准输出。

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

样例输入

样例输出

样例解释

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

子任务

各测试点的数据规模和性质如下表:

编号$n$$K$特殊性质编号$n$$K$特殊性质
1$\leq 5$$\leq 3$11$\leq 1000$$\leq 2$A
2$\leq 10$12
3$\leq 15$13
4$\leq 20$14
5$\leq 1000$$=1$A15
616
717$\leq 3$A
818
919
1020

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

对于所有的数据,保证 $1 \leq f_i \leq i, 2 \leq n \leq 1000$。

题目来源

NOI 2018 Day 2


关于标准输出的说明(最后更新:2018年10月23日)

标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。

如果你的程序要进行大量输出,请考虑这一点。




Judge Duck Online | 评测鸭在线
Server Time: 2019-08-22 21:15:30 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用