#PQJ1877x9911. QOJ 1877_9911
QOJ 1877_9911
IOI2025 中国国家集训队集中培训 第二试路南柯(nanke) 路南柯(nanke) 【题目描述】 称一个1 ∼n 的排列{p} = {p1, p2, · · · , pn} 是一棵n 个点、点编号为1 至n 的树 T 的.拓.扑.序.列,当且仅当对于任意1 ≤i < n,恰好存在唯一的j > i 满足pi 与pj 之间 有连边。 给定树T,你需要给出尽可能少的该树的拓扑序列{p1}, {p2}, · · · , {pk},使得有且 仅有树T 满足{p1}, {p2}, · · · , {pk} 均为该树的合法拓扑序列。 【输入格式】 从标准输入读入数据。 .本.题.有.多.组.测.试.数.据。输入第一行一个正整数T,表示测试数据组数,接下来依次 输入每组测试数据。 对于每组数据,输入第一行一个正整数n,表示给定树的大小。接下来n −1 行,每 行两个正整数u, v 描述树中存在的一条边。 【输出格式】 输出到标准输出。 对于每组数据,输出第一行一个正整数k 表示你给出的拓扑序列数量,接下来k 行,每行输出一个1 ∼n 的排列,描述你给出的拓扑序列。你需要保证1 ≤k ≤n,且这 k 个拓扑序列均为对应输入的合法拓扑序列,且只有一棵树满足这些拓扑序列都是其合 法拓扑序列。 【样例1 输入】 2 1 5 2 2 3 3 3 1 4 5 1 5 5 4 6 5 7 1 4 8 2 3 9 3 1 10 5 3 11 第8 页 共9 页 IOI2025 中国国家集训队集中培训 第二试路南柯(nanke) 【样例1 输出】 2 1 2 3 1 5 4 2 4 5 1 3 2 3 2 4 4 1 5 3 2 5 2 5 3 4 1 6 【子任务】 对于所有测试数据,1 ≤T ≤100,3 ≤n ≤100,1 ≤u, v ≤n。 本题共有两个测试点。 测试点编号 分值 T n 1 20 = 10 = 10 = 102 = 102 2 80 特别地,所有测试点中每组数据均为从所有n 个点的有标号树中等概率随机选择 生成得到的。 【评分方式】 对于一个测试点内部的某组数据:
- 你需要保证k 以及你输出的序列中每个数都为[1, n] 范围内的正整数,否则.整.个 .测.试.点将会获得0 分。
- 若你给出的序列中存在一个不是输入给定树的拓扑序列,那么你.这.组.数.据的得分 比例将会是0。
- 若存在多棵树满足其这些序列都是其合法的拓扑序列,那么你.这.组.数.据的得分比 例将会是0。
- 否则如果最优解为K,而你构造的序列数量为k,那么你.这.组.数.据的得分比例将 为0.97k−K。 一个测试点的得分比例将会是该测试点内所有数据的得分比例的.平.均.值,一个测试 点的实际得分值将会是其总分乘以得分比例。 第9 页 共9 页