定理：对于一个有 \(n\) 个节点的无根树，它的结构可以有 \(n^{n-2}\) 种可能。

至于证明，我们可以用 \(prufer\)序列 来证明。

\(prufer\)序列

度娘给出的定义是： \(Prufer\)数列 是无根树的一种数列。在组合数学中, \(Prufer\)数列 由有一个对于顶点标过号的树转化来的数列，点数为n的树转化来的 \(Prufer\)数列 长度为n-2。

给出无根树和 \(prufer\)序列 和无根树之间的转化过程。

（1）无根树转 \(prufer\)序列

1.找到编号最小的度数为 \(1\)的点

2.删除该节点并在序列中添加与该节点相连的节点的编号

3.重复1,2操作，直到整棵树只剩下两个节点

（2） \(prufer\)序列 转无根树

1.每次取出 \(prufer\)序列 中最前面的元素u

2.在点集中找到编号最小的没有在 \(prufer\)序列 中出现的元素v，给u,v连边然后分别删除

3.最后在点集中剩下两个节点，给它们连边

以上两种操作都可以用set维护，时间复杂度 \(O(n log n)\) .

那它又有什么性质呢？

1.prufer序列中某个编号出现的次数就等于这个编号的节点在无根树中的度数-1

2.一棵n个节点的无根树唯一地对应了一个长度为n-2的数列，数列中的每个数都在1到n的范围内。（这是这个公式所需的性质）

因此，对于一棵已知有 \(n\) 个结点的无根树，一定有一个 \(n−2\) 长度的序列，那么，我们枚举所有长度为 \(n-2\) 的序列，发现其与所有可能形态的无根树一一对应。而这种序列，根据乘法原理，有 \(n^{n-2}\) 个序列。至于有根树也好说，我们枚举 \(n\) 个节点分别为根即可，则有 \(n^{n-1}\) 个不同结构的树。