#1895. 颠倒歌
颠倒歌
颠倒歌
题目描述
IOI2025 中国国家集训队集中培训 第二试颠倒歌(diandao) 颠倒歌(diandao) 【题目描述】 对于树T(V, E) 和S ⊆V ,记f(S, T) 表示T 的对S 的导出子图(即仅保留S 中 的点和两端都在S 中的边得到的图)中度数小于等于1 的点的数量。 对于两棵树T1(V1, E1), T2(V2, E2),若V1 = V2,我们称T1 ≼T2 当且仅当对于任意 S2 ⊆V2,存在S1 满足S2 ⊆S1 ⊆V1 且f(S1, T1) ≤f(S2, T2)。 称T1, T2 等价当T1 ≼T2 且T2 ≼T1,记作T1 ∼T2。该等价关系将n 个点的有标 号树划分成若干等价类。 问:
- 给定k 棵n 个点的树T1, T2 . . . , Tk,求满足T ≼Ti, ∀1 ≤i ≤k 的.有.标.号.树T .构 .成.的.等.价.类数量。
- 给定k 棵n 个点的树T1, T2 . . . , Tk,求满足Ti ≼T, ∀1 ≤i ≤k 的.有.标.号.树T 数 量。 注意两问的计数对象不同。两问答案均对998, 244, 353 取模。 保证答案取模后非0。 【输入格式】 从标准输入读入数据。 输入第一行一个整数p,其中p ∈{0, 1},p = 0 表示询问第一问,否则表示询问第 二问。 接下来一行两个正整数k, n,分别表示输入树的数量以及点数。 接下来依次输入k 棵树,对于每棵树输入n −1 行每行两个正整数u, v 描述树中的 一条边。 【输出格式】 输出到标准输出。 输出一行一个整数表示答案对998, 244, 353 取模后的结果。 【样例1 输入】 0 1 1 4 2 1 2 3 1 3 4 1 4 5 第5 页 共9 页 IOI2025 中国国家集训队集中培训 第二试颠倒歌(diandao) 【样例1 输出】 2 1 【样例1 解释】 可以证明4 个点的有标号树被划分成了5 个等价类,所有的链在同一个等价类,而 其它分别以每个点为菊花中心对应一个等价类。 可以验证链对应的等价类和该树本身所在的等价类均满足要求,而其他等价类不满 足要求。 【样例2 输入】 1 1 1 4 2 1 2 3 2 3 4 3 4 5 【样例2 输出】 16 1 【样例2 解释】 可以验证所有4 个点的有标号树共16 个均满足要求。 【样例3】 见题目目录下的3.in 与3.ans。 【样例4】 见题目目录下的4.in 与4.ans。 【样例5】 见题目目录下的5.in 与5.ans。 第6 页 共9 页 IOI2025 中国国家集训队集中培训 第二试颠倒歌(diandao) 【样例6】 见题目目录下的6.in 与6.ans。 【样例7】 见题目目录下的7.in 与7.ans。 【样例8】 见题目目录下的8.in 与8.ans。 【样例9】 见题目目录下的9.in 与9.ans。 【样例10】 见题目目录下的10.in 与10.ans。 【子任务】 对于所有数据,保证p ∈{0, 1},3 ≤n ≤5000,1 ≤k ≤1000,1 ≤u, v ≤n,答案 取模后不等于0。 子任务编号 树形态 分数 p n k 1 10 无特殊形态 ∈{0, 1} ≤8 ≤4 2 4 菊花 ≤1 3 8 ≤200 4 9 ≤2 = 0 无特殊形态 5 10 ≤40 6 14 ≤103 ≤5, 000 7 7 链 ≤1 8 7 ≤200 9 10 ≤2 = 1 无特殊形态 10 10 ≤40 11 11 ≤103 ≤5, 000 “树形态”中,“菊花”指存在一个向所有点有直接连边的点,“链”指所有点度数 不超过2。 第7 页 共9 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
0
1 4
1 2
1 3
1 4
2
样例 2
1
1 4
1 2
2 3
3 4
16