Prufer数列是无根树的一种数列。在组合数学中，Prufer数列由有一个对于顶点标过号
的树转化来的数列，点数为n的树转化来的Prufer数列长度为n-2。它可以通过简单的
迭代方法计算出来。它由Heinz Prufer于1918年在证明cayley定理时首次提出。
一种生成Prufer序列的方法是迭代删点，直到原图仅剩两个点。对于一棵顶点已经
经过编号的树T，顶点的编号为{1,2,...,n}，在第i步时，移去所有叶子节点（度为1
的顶点）中标号最小的顶点和相连的边，并把与它相邻的点的编号加入Prufer序列
中，重复以上步骤直到原图仅剩2个顶点。
例子：
以下边的树为例子，首先在所有叶子节点中编号最小的点是
2，和它相邻的点的编号是3，将3加入序列并删除编号为2的
点。接下来删除的点是4，5被加入序列，然后删除5，1被加入
序列，1被删除，3被加入序列，此时原图仅剩两个点（即3和
6），Prufer序列构建完成，为{3,5,1,3}
将Prufer数列转化成树的方法
设{a1,a2,..an-2}为一棵有n个节点的树的Prufer序列，另建一个集合G含有元素{1..n}，
找出集合中最小的未在Prufer序列中出现过的数，将该点与Prufer序列中首项连一条
边，并将该点和Prufer序列首项删除，重复操作n-2次，将集合中剩余的两个点之间连
边即可。
例子：
仍为上面的树，Prufer序列为{3,5,1,3}，开始时G={1,2,3,4,5,6}，未出现的编号最小的
点是2，将2和3连边，并删去Prufer序列首项和G中的2。接下来连的边为{4,5},{1,5},
{1,3},此时集合G中仅剩3和6，在3和6之间连边，原树恢复。
再看看Cayley公式：
Cayley公式是说，一个完全图K_n有n^(n-2)棵生成树，换句话说n个节点的带标
号的无根树有n^(n-2)个。
下面看看bzoj1430：
1430: 小猴打架
Submit: 542 Solved: 389
[Submit][Status][Discuss]
Description
一开始森林里面有N只互不相识的小猴子，它们经常打架，但打架的双方都必须不是好朋友。每次打完架后，打架的双方以及它们的好朋友就会互相认识，成为好朋友。经过N-1次打架之后，整个森林的小猴都会成为好朋友。 现在的问题是，总共有多少种不同的打架过程。 比如当N=3时，就有{1-2,1-3}{1-2,2-3}{1-3,1-2}{1-3,2-3}{2-3,1-2}{2-3,1-3}六种不同的打架过程。
Input
一个整数N。
Output
一行，方案数mod 9999991。
Sample Input
4
Sample Output
96
HINT
50%的数据N<=10^3。
100%的数据N<=10^6。
由上文中转化prufer编码的方式可知，对于一棵N节点树来说，其prufer编码有N-2位，而生成树的个数就是prufer的个数。那么，就是N^(N-2)个，而加边顺序有(N-1)!种，根据乘法原理，则共有(N-1)!*(N^(N-2))个，这即为答案。
附AC代码：
#include<iostream> #include<cstdio> #include<cstdlib> #include<cmath> #include<cstring> #include<algorithm> #include<cmath> #include<climits> #define mod 9999991 using namespace std; typedef long long ll; int n;ll tmp=1,txp=1; int main() {scanf("%d",&n);for(ll i=1;i<=n-2;i++)tmp=tmp*i%mod,txp=txp*n%mod;tmp=tmp*(n-1)%mod;printf("%lld\n",tmp*txp%mod); }