PDF《CCF NOI 2018》

20 表格中的特殊性质如下: ? 特殊性质 S 1:对于任意 i, j,保证 xi 到yi 的最短路径所经过的编号最小的节点 不同于 xj 到yj 的最短路径所经过的编号最小的节点;

? 特殊性质 S 2:对于任意 i,保证 xi 到yi 的最短路径所经过的编号最小的节点为 节点 1. 对于所有的数据,1 ≤ n ≤

5 *

104 ,0 ≤ m ≤

105 ,0 ≤ ci ≤

109 ,0 ≤ vi ≤

1010 * n.每 个测试点中,所有 n 的和不会超过 1, 000, 233,所有 m 的和不会超过 2, 000, 233. 第8页共11 页 全国青少年信息学奥林匹克竞赛 第二试 多边形(polygon) 多边形(polygon) 【题目描述】 久莲是一个喜欢出题的女孩子. 在今年的 World Final 结束以后,久莲特别喜欢计算几何,于是她打算在 NOI 的 考场上也出一个计算几何:这是一道只有题目名字和计算几何相关的题目. 首先,久莲给出了一棵 n(n ≥ 2) 个节点的有根树 T,根节点编号为 1.定义叶子节 点为除了根以外所有度数恰好为

1 的节点.下图是一个树 T 的例子,其中叶子节点集 合为 {3, 4, 5}. 接着通过这棵树,久莲构造了一个序列 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 都如下图所示: 现在久莲想让你来计算一下 G 中不同的哈密尔顿回路数量有多少条,答案可能很 大,请对

998244353 取模后输出. 第9页共11 页 全国青少年信息学奥林匹克竞赛 第二试 多边形(polygon) 下面是一些补充定义: ? 无重边无自环的无向图 G 的一条哈密尔顿回路 H 是G中边的一个子集,其中 每一个点恰好有两条不同的相邻边在 H 中,且任意两个点都可以通过 H 中的边 直接或间接到达. ? 无重边无自环的无向图 G 的两条哈密尔顿回路 H1, H2 是不同的当且仅当存在一 条边 e 使得 e 在H1 中且不在 H2 中. 【输入格式】 从文件 polygon.in 中读入数据. 第一行输入两个整数 n, K,表示树 T 的点数以及久莲选定的参数 K. 第二行输入 n ?

1 个整数 fi(1 ≤ fi ≤ i),其中 fi 表示树 T 上存在边 ( fi, i + 1). 【输出格式】 输出到文件 polygon.out 中. 输出一行一个整数,表示哈密尔顿回路数量对

998244353 取模后的结果. 【样例

1 输入】

5 1

1 1

2 2 【样例

1 输出】

2 第10 页共11 页 全国青少年信息学奥林匹克竞赛 第二试 多边形(polygon) 【样例

1 解释】 该样例和题面中的例子完全相同.两条哈密尔顿回路经过节点的顺序分别为 (1, 2, 4, 5, 3) 和(1, 2, 5, 4, 3). 【子任务】 各测试点的数据规模和性质如下表: 编号 n K 特殊性质 编号 n K 特殊性质