分析：
我其实想到链状怎么做了，没有往下多想。一直想用组合做。
最后看到CLJ的题解，才发现我已经想对了一半。。。
对于一个链来说，设Dp[i]为长度为i的链和一个“中心”的生成树数量，可以Dp之。。
然后考虑环，枚举1节点所在的环的长度，设为Len，那么这个环的位置有Len种情况，这个环与中心连接也有Len种情况，那么这个节点对答案的贡献就是Len^2*Dp[n-Len]。。
转自：http://hi.baidu.com/wjbzbmr/item/3f5e90f02b913ed66225d201
View Code
1 #include <cstring> 2 #include <cstdlib> 3 #include <cstdio> 4 #include <algorithm> 5 #include <iostream> 6 7 #define N 50 8 9 using namespace std; 10 11 struct BIGN 12 { 13 int a[N]; 14 }dp[110],ans; 15 16 int n; 17 18 inline BIGN operator +(BIGN a,BIGN b) 19 { 20 BIGN c; memset(c.a,0,sizeof c.a); 21 c.a[0]=max(a.a[0],b.a[0]); 22 int jin=0; 23 for(int i=1;i<=c.a[0];i++) 24 { 25 jin+=a.a[i]+b.a[i]; 26 c.a[i]=jin%10000; 27 jin/=10000; 28 } 29 while(jin) c.a[++c.a[0]]=jin%10000,jin/=10000; 30 return c; 31 } 32 33 inline BIGN operator *(BIGN a,int b) 34 { 35 BIGN c; memset(c.a,0,sizeof c.a); 36 int jin=0; 37 for(int i=1;i<=a.a[0];i++) 38 { 39 jin+=c.a[i]+a.a[i]*b; 40 c.a[i]=jin%10000; 41 jin/=10000; 42 } 43 c.a[0]=a.a[0]; 44 while(jin) c.a[++c.a[0]]=jin%10000,jin/=10000; 45 return c; 46 } 47 48 void prev() 49 { 50 dp[0].a[0]=dp[0].a[1]=1; 51 dp[1].a[1]=dp[1].a[0]=1; 52 for(int i=2;i<=100;i++) 53 { 54 dp[i].a[1]=0;dp[i].a[0]=1; 55 for(int j=1;j<=i;j++) 56 dp[i]=dp[i]+dp[i-j]*j; 57 } 58 59 } 60 61 void prt(const BIGN &a) 62 { 63 printf("%d",a.a[a.a[0]]); 64 for(int i=a.a[0]-1;i>=1;i--) printf("%.4d",a.a[i]); 65 puts(""); 66 } 67 68 int main() 69 { 70 prev(); 71 scanf("%d",&n); 72 ans.a[1]=0; ans.a[0]=1; 73 for(int i=1;i<=n;i++) 74 ans=ans+dp[n-i]*(i*i); 75 prt(ans); 76 return 0; 77 }