1136. Tree II

单点时限: 2.0 sec

内存限制: 256 MB

树是计算机中非常重要的非线性结构。对树本身的形态进行思考与研究,是一个 十分有趣且具有挑战性的过程。 我们对一个树的正式定义是:

  1. 一个结点 x 组成的集 {x} 是一株树。 这个结点 x 也是这株树的根。

  2. 假设 x 是一个结点, T1 ,T2 ,…,TK 是 K 株互不相交的树,我们可以构造一株新树:令 x 为根,并有 K 条边由 x 指向树 T1 ,T2 ,…,TK。这些边也叫做 分支,T1 ,T2 ,…,TK 称作根为 x 的树的子树(subtree)。

――《数据结构》 大连理工大学出版社

连通的无圈图称为自由树。如果选定自由树中的某个顶点 作树根,以树根为起点对每条边定向,就能把一棵自由树变成一棵通常的树。

――《数据结构与算法》

自由树与通常所说的树很相似,它包括有结点和分支, 但不含有根。自由树结点间只有相邻关系,而不存在父子结点关系。 容易发现,对某棵自由树,指定其一个结点为根结点后, 我们将得到一棵有根树。 对于两棵自由树甲和乙,任取自由树甲的某个结点作为 根结点,形成一棵有根树丙。若存在以自由树乙的某结点为根的有根树丁与丙同构, 则称甲乙两树同构。

输入格式

输入包含一个非负整数序列。对于每个输入的 N (1<=N<=200),求出 结点个数为 N 的自由树总数。输入以 0 结束。

输出格式

每个结果一行

样例

Input
1
2
3
0
Output
1
1
1

0 人解决,6 人已尝试。

0 份提交通过,共有 16 份提交。

9.9 EMB 奖励。

创建: 15 年,7 月前.

修改: 5 年,3 月前.

最后提交: 2 年前.

来源: partychen

题目标签