在一张图上有 \\(n\\) 个节点，可以产生的生成树个数为 \\(n^{n-2}\\)
如果指定根就是：\\(n^{n-1}\\)（一棵树可以有\\(n\\)个根，变化出 \\(n\\) 中方案乘一下）
证明一一对应法。
设\\(n\\)个点为：\\(1,2,... n\\).
假设 \\(T\\) 是其中一棵树，树叶中有标号最小的，设为 \\(a_1\\) ， \\(a_1\\) 的临界点为\\(b_1\\)
从图中消去 \\(a_1\\) 点和边 \\((a_1,b_1)\\) ，\\(b_1\\) 点便成为消去后余下的树 \\(T_1\\) 的叶子节点。
在树 \\(T_1\\) 中继续寻找标号最小的树叶，设为 \\(a_2\\)，\\(a_2\\) 的邻接点为 \\(b_2\\)，从 T_1 中消去 a_2 及边 \\((a2,b2)\\)。
如此步骤共执行 \\(n-2\\) 次，直到最后只剩下一条边为止.于是一棵树对应一序列 $ b$
\\(b_1,b_2,⋯,b_{n-2}\\) 是 \\(1\\) 到 \\(n\\) 的数，并且允许重复。
反过来从 \\(b\\) 可以恢复树 \\(T\\) 本身，方法如下：
一个是顶点标号的有序序列
\\[a_{1 \\rightarrow n}\\]
另一个是生成的序列
\\[{b_{1 \\rightarrow n}}\\]
过程：在序列 \\(a\\) 中找出第一个不出现在序列 \\(b\\) 中的数
这个数显然便是 \\(a_1\\)，同时形成的边 \\((a_1,b_1)\\)，并从 \\(a\\) 中消去 \\(a_1\\) ,从 \\(b\\) 中消去\\(b_1\\)
在余下的序列中继续以上的步骤 \\(n-3\\) 次，直到序列 \\(b\\) 为空集为止。这
时序列(1)剩下的两个数\\(a_ k,b_k\\)，边\\((a_k,b_k)\\)是树 \\(T\\) 的最后一条边。
上面的过程说明过 \\(n\\) 个已知标号的顶点的树和序列 \\({b_{1 \\rightarrow n}}\\) 一一对应
根据乘法法则可得，过 \\(n\\) 个有标号（相当于互异）的顶点的树的数目，为 \\(n^{n-2}\\) 个.
\\[Q.A.D\\]
\\(P.s.\\) 博主知道是 \\(QED\\)
挺爽的，学会了就可以来十行之内写 \\(LGOJ\\) 蓝牌题了
例题1.LGOJ4430 小猴打架link
这个题就可以拿定理水了吧……
首先树的构成有 \\(n^{n-2}\\) 种，然后每一棵树有 \\((n-1) \\space!\\) 中构造方式（\\(n-1\\)条边，不限定顺序，然后是小学知识了吧……）
答案就是：\\((n-1) \\space ! \\times n^{n-2}\\)
这种结论题还是挺恐怖的，猜错了就……
2.LGOJ4981 父子link
太裸了……直接快速幂加结论就完了
来源：https://www.cnblogs.com/yspm/p/12389391.html
本文链接： http://cayley.immuno-online.com/view-748853.html
