UOJ Logo Universal Online Judge

UOJ

#183. 【ZJOI2016】随机树生成器

附件下载 统计

小Y最近有了一个随机数生成器(random number generator)。小Y想用这个随机数生成器生成 n 个节点的树。树为一种没有环的无向连通图。

经过小Y的研究,她发现了 4 种随机树生成方法。

第一种方法为首先生成一个 1n 的全排列 p1,p2,,pn。接着对于所有的节点 i(2in),由 pipj 连一条边,其中 j1i1 中的随机整数。

第二种方法为首先生成一个 1n 的全排列 p1,p2,,pn。接着对于所有的节点 i(2in),由 pipj 连一条边,其中 ji2i1 中的随机整数。

第三种方法为首先有一个 n 个点的图,里面没有边。接着等概率地随机生成点对 u,v ,如果当前图中 u,v 不连通,那么将边 (u,v) 加入到图中。重复这个过程,直到这个图连通为止。

第四种方法为在所有 n 个点的不同的有标号的树中,等概率地随机选取一棵树。两个树是不同的当且仅当存在一条边 (u,v) 只出现在其中一棵树中。比如 (1,2),(1,3)(1,2),(2,3) 是两棵不同的树。

小Y用这四种方法生成了很多棵 n 个节点的树,但她忘记了这些树分别由哪种方法生成的。你能帮帮她辨认这些树由哪种随机方法生成吗?

在这个题目中令 n=1000,也就是小Y生成的树的节点个数都为 1000

输入格式

第一行包含 1 个正整数 T,表示是第 T 组测试数据。

接下来一个正整数 m,表示有 m 棵树。

对于每棵树,共 n1 行。每行包含 2 个正整数 u,v,表示这棵树中有一条节点 u 与节点 v 之间的边。

输出格式

输出共 m 行,每行一个 14 之间的正整数,表示这棵树随机生成的方式。

样例一

见样例数据下载。

限制与约定

测试点编号m约定
1=2000只会出现第 1,2 种生成方式
2=3000只会出现第 1,2,3 种生成方式
3只会出现第 1,3,4 种生成方式
4=4000
5

对于所有的测试数据,保证输入的树是由上述四种方式随机生成。

对于每个测试点,保证每种可能出现的生成方式恰好出现 1000 次。

评分方法

对于每个测试点,有 10 个评分参数 a10,a9,a8,,a1

如果你的输出中错误的答案个数为 x, 那么你将获得 2s 的分数,其中 s 为满足 xas 最大的整数。如果 x>a1,那么你将获得 0 分。

如果输出格式有异常你将同样获得 0 分,请确保你的输出中共有 m 行,每行为一个 14 之间的正整数。

对于每个测试点的具体评分参数见样例数据下载中的 scores。

时间限制:3s

空间限制:256MB

下载

样例数据下载