#1544. 「eJOI2018」互素树 加强版

「eJOI2018」互素树 加强版

Cannot parse: undefinedms error parsing time

题目描述

本题为「eJOI2018」互素树 加强版。

设有一棵有 nn 个结点的树,其结点编号为 11nn
对于其中的任意一条边 (u,v)(u, v) ,如果存在一个正整数 d>1d>1 满足 du,dv d \mid u, d\mid v ,我们称它为一条坏的边
下图中的树有三条坏的边—— (6,4)(6, 4)(都被 22 整除), (2,6)(2, 6)(都被 22 整除), (3,6)(3, 6)(都被 33 整除)。

你的任务是将结点重新编号,使得图中坏的边的数量尽量少。
对于上图中的树,按照下图中的方式将结点重新编号,会只剩一条坏的边 (3,6)(3, 6)

重新编号后,坏的边越少,你的得分越高。

这是一道提交答案题。你应当点击上方的「附加文件」下载输入文件(其中,00为样例,01~05为测试数据;无需提交样例的答案),然后在本地运行你的程序,将输出结果上传。

输入格式

每个测试点中有多组测试数据。
第一行,一个整数 TT,表示测试数据组数。
每组测试数据共 nn 行,其中 nn 表示树的结点个数。
第一行,一个整数 nn
接下来 n1n-1 行,每行两个整数 uuv (1u,vn)v\ ( 1 \le u, v \le n),表示一条边 (u,v)(u,v)

每个输入文件中,每棵树的结点个数相同。

输出格式

对于每组测试数据,输出一行 nn 个整数,表示原先编号为 11nn 的结点的新编号。
每个结点的编号必须不同,也就是说同一组测试数据中输出的 nn 个整数必须互不相同。

样例 1

2
6
1 3
3 5
3 6
6 4
6 2
6
1 2
1 3
1 4
1 5
1 6
2 5 3 1 4 6
5 1 2 3 4 6
2
6
1 3
3 5
3 6
6 4
6 2
6
1 2
1 3
1 4
1 5
1 6
4 5 1 3 6 2
5 4 6 1 3 2

第一组测试数据已经在题目描述中讨论过。输出 1 中有一条坏的边 (3,6)(3, 6),输出 2 中没有坏的边。

第二组测试数据中,输出 1 和输出 2 都没有出现坏的边。

样例中,M=2×5=10M=2\times 5 =10

对于输出 1,X=1,R=110=0.1X = 1, R = \frac1{10}=0.1,该输出将得到 55 分。

对于输出 2,X=0,R=010=0X = 0, R = \frac0{10} = 0,该输出将得到 1010 分。

数据范围与提示

计分方式

对于每个测试点,设所有树的总边数为 M=T×(n1)M=T \times (n-1),你的输出中坏的边数为 XX,记 R=XMR=\dfrac{X}{M} ,你的得分与 RR 的关系如下:

RR 得分 RR 得分
0.1<R0.20.1 < R \le 0.2 22 0.001<R0.0040.001 < R \le 0.004 1212
0.04<R0.10.04 < R \le 0.1 44 0.0004<R0.0010.0004 < R \le 0.001 1414
0.02<R0.040.02 < R \le 0.04 66 0.0002<R0.00040.0002 < R \le 0.0004 1616
0.01<R0.020.01 < R \le 0.02 88 0<R0.00020 < R \le 0.0002 1818
0.004<R0.010.004 < R \le 0.01 1010 R=0R=0 2020

R>0.2R > 0.2 时,不能得分。

对于所有的测试点,保证存在 X=0X=0 的输出。对于每组数据,标准程序得到 X=0X=0 的输出的运行时间不超过 700700 秒。

数据范围

测试点编号 样例 1 2 3 4 5
文件名 00 01 02 03 04 05
TT 22 1010 55 33 22 11
nn 66 5000050000