HBC21122[NOI2018]多边形题解

全网最全C++题库，助您快速提升编程技能！题库丰富多样，涵盖各个领域，让您在练习中不断成长！

久莲是一个喜欢出题的女孩子， 在今年的 World Final 结束以后，久莲特别喜欢计算几何，于是她打算在 NOI 的 考场上也出一个计算几何：这是一道只有题目名字和计算几何相关的题目， 首先，久莲给出了一棵 n(n ≥ 2) 个节点的有根树 T，根节点编号为 1，定义叶子节 点为除了根以外所有度数恰好为 1 的节点，下图是一个树 T 的例子，其中叶子节点集 合为 {3, 4,

久莲是一个喜欢出题的女孩子。  在今年的 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 取模后输出。  下面是一些补充定义：  • 无重边无自环的无向图 G 的一条哈密尔顿回路 H 是 G 中边的一个子集，其中 每一个点恰好有两条不同的相邻边在 H 中，且任意两个点都可以通过 H 中的边 直接或间接到达。  • 无重边无自环的无向图 G 的两条哈密尔顿回路 H1, H2 是不同的当且仅当存在一 条边 e 使得 e 在 H1 中且不在 H2 中。 

不断挑战自我，才能突破极限！全网最全C++题库，让您在编程道路上越走越远。

标签： HBC21122[NOI2018]多边形题解