Prufer序列
在一棵n个节点带标号树中，我们认为度数为1的点为叶子。n个点的树的Prufer序列是经过下面流程得到的一个长度为n-2的序列。
1.若当前树中只剩下两个点，退出，否则执行2。
2.找到树中编号最小的节点，将与它相连的那个点的编号加入Prufer序列的末尾，并将这个叶子删除。返回1。
显然，每棵树都唯一对应一个Prufer序列，而每个Prufer序列也唯一对应一棵树。可以通过一下流程得到这棵树。
1.令A={1,2,...,n}，不断重复2直到Prufer序列为空。
2.找到A中最小的不在Prufer序列中的点，将其与Prufer序列首元素连边，然后同时删除这个点与序列首元素。
3.此时A中还剩下两个点，将这两个点连边。
根据以上流程，不难发现：若点i在树中的度数为a[i]，则它在Prufer序列中会出现a[i]-1次。
Cayley's Formula
Prufer序列中的每个元素都可以从1取到n，且每种方案会唯一对应一棵带标号无根树。
所以，由于Prufer序列共有$n^{n-2}$个，n个点的带标号无根树就有$n^{n-2}$种。
拓展：
1.显然，n个点的带标号有根树有$n^{n-2}$种。
2.当树中每个点的度数$a_i$都已经确定后，由Prufer序列得，满足条件的树共有$frac{(n-2)!}{prod a_i!}$种。
例题：BZOJ1005,BZOJ1211,BZOJ1430
Generalized Cayley's Formula
已知n,k，求f(n,m)表示n个点组成的共有m棵树的森林，且1,2,...,m分别属于不同的树，的方案数。
先给出结论：$f(n,m)=mcdot n^{n-m-1}$。
（显然可以发现$f(n,1)=n^{n-2}$）
证明：
显然，$f(1,1)=0$，$f(n,0)=0(ngeq 1)$。
数学归纳，假设对于所有$i<n$的$f(i,j)$都已证明。
考虑1号点属于的那棵树，枚举1号点的度数i，则删除后这张图会变成n-1个点，m+i-1棵树。
$f(n,m)=sumlimits_{i=0}^{n-m}inom{n-m}{i}f(n-1,m+i-1)$
将原式代入，有$f(n,m)=sumlimits_{i=0}^{n-m}inom{n-m}{i}(m+i-1)(n-1)^{n-m-i-1}=mn^{n-m-1}$
命题得证。
拓展：
显然n个点组成有根树森林的方案为$sumlimits_{k=1}^{n}n^{n-k-1} imes k imes inom{n}{k}$
应用：CF1109D
给定n,m,a,b，求有多少个n个点的带标号无根树，满足所有边权在[1,m]中，且a到b的简单路径长度为m。
显然枚举a,b中的边数，那么a,b中间的点有$P_{n-2}^{i-1}$种方案，这中间i条边的边权共有$C_{m-1}^{i-1}$种方案，其余边权有$m^{n-i-1}$种方案，而剩下的就是n个点组成i+1棵树，其中在a,b简单路径上的i+1个点分别属于其中一棵树的方案数，也就是$f(n,i+1)=(i+1)n^{n-i-2}$。
定理拓展：
n个带权的点，定义每条边的权值为相连的两个点的权值之积，定义一棵树的权值是所有边的权值之积，求所有树的权值和。
相当于每棵树中每个点的权值的度数次方的和。考虑Prufer序列，每个点都恰出现度数-1次。于是根据乘法分配律，答案为(所有点权值之积)*(所有点权值之和)^(n-2)。
这个推论包含了上面所有定理。当所有点权值取1时，就是Cayley's Formula。当将点1~m缩成一个权值为m的点时，就是Generalized Cayley's Formula。
以上所有似乎都可以用Matrix Tree那一套理论通过化简行列式得到。