其实，就是求n个点的生成树的个数。
下面就是如果求生成树的个数： Matrix-Tree定理(Kirchhoff矩阵-树定理)。Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前，我们首先明确几个概念： 1、G的度数矩阵D[G]是一个n*n的矩阵，并且满足：当i≠j时,dij=0；当i=j时，dij等于vi的度数。 2、G的邻接矩阵A[G]也是一个n*n的矩阵， 并且满足：如果vi、vj之间有边直接相连，则aij=1，否则为0。 我们定义G的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G]，则Matrix-Tree定理可以描述为：G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式，就是对于r(1≤r≤n)，将C[G]的第r行、第r列同时去掉后得到的新矩阵，用Cr[G]表示。 获得图G：
for (int i=0;i<N;i++) for (int j=0;j<N;j++) g[i][j]=0; while(M--) { int a,b; scanf("%d%d",&a,&b); g[a-1][b-1]=g[b-1][a-1]=1; }获得矩阵C[G] 因为度数矩阵在i==j的时候才是有值，而邻接矩阵一般不自连，所以可以直接处理出C[G]
for(int i=0;i<N;i++) { int d=0; for(int j=0;j<N;j++) if(g[i][j]) { a[i][j]=-1 d++; } a[i][i]=d; }然后高斯消元求n-1行列式的值就好了
#define zero(x)((x>0? x:-x)<1e-15) double det(int n) { int i,j,k,sign=0; double ret=1,t; for(i=0;i<n;i++) { if(zero(a[i][i])) { for(j = i + 1; j < n; j++) if(!zero(a[j][i])) break; if(j==n) return 0; for(k=i;k<n;k++) t=a[i][k],a[i][k]=a[j][k],a[j][k]=t; sign++; } ret*= a[i][i]; for(k=i+1;k<n;k++) a[i][k]/=a[i][i]; for(j=i+1;j<n;j++) for(k=i+1;k<n;k++) a[j][k]-=a[j][i]*a[i][k]; } if(sign&1) ret=-ret; return ret; }然而…. 这题的图都是满边的… 所以可以直接推导出公式。 设中心点为0点，其余点都按顺时针编号。即可写出C[G]矩阵，求出C[G]矩阵的n-1阶行列式，即为答案。 证明传送门：http://blog.csdn.net/le_ballon_rouge/article/details/47609531 ans=3×G(n−1)−2×G(n−2)−2; 由于数字较大，需要高精度。 直接java
import java.io.*; import java.math.*; import java.util.*; public class Main { public static void main(String[] args) { BigInteger a[]=new BigInteger[105]; Scanner in= new Scanner(System.in); int n=in.nextInt(); a[1]=BigInteger.ONE; a[2]=BigInteger.valueOf(5); for(int i=3;i<=n;i++) a[i]=a[i-1].multiply(BigInteger.valueOf(3)).subtract(a[i-2].subtract(BigInteger.valueOf(2))); System.out.println(a[n]); } }