1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
| #include<algorithm> #include<iostream> #include<iomanip> #include<cstring> #include<cstdlib> #include<vector> #include<cstdio> #include<cmath> #include<queue> using namespace std; inline const int Get_Int() { int num=0,bj=1; char x=getchar(); while(x<'0'||x>'9') { if(x=='-')bj=-1; x=getchar(); } while(x>='0'&&x<='9') { num=num*10+x-'0'; x=getchar(); } return num*bj; } const int maxn=1005,mod=10007; int T,n,Min,core1,core2,Core,tot,sum,ans,Size[maxn],f[maxn][maxn],g[205][205][205],Maxd[maxn],son[maxn]; bool ifunion; vector<int>edges[maxn]; void AddEdge(int x,int y) { edges[x].push_back(y); } void Clear() { Min=0x7fffffff/2; core1=core2=Core=ifunion=tot=sum=0; ans=1; for(int i=1; i<=n+1; i++)edges[i].clear(); memset(Size,0,sizeof(Size)); memset(Maxd,0,sizeof(Maxd)); memset(f,0,sizeof(f)); memset(g,0,sizeof(g)); } void Dfs(int Now,int father) { Size[Now]=1; for(int i=0; i<edges[Now].size(); i++) { int Next=edges[Now][i]; if(Next==father)continue; Dfs(Next,Now); Size[Now]+=Size[Next]; Maxd[Now]=max(Maxd[Now],Size[Next]); } Maxd[Now]=max(Maxd[Now],n-Size[Now]); if(Maxd[Now]<Min) { Min=Maxd[Now]; core1=Now; core2=0; } else if(Maxd[Now]==Min)core2=Now; } void TreeDp(int Now,int father) { Size[Now]=1; f[Now][0]=f[Now][1]=1; for(int k=0; k<edges[Now].size(); k++) { int& Next=edges[Now][k]; if(Next==father)continue; TreeDp(Next,Now); Size[Now]+=Size[Next]; for(int i=Size[Now]; i>=1; i--) for(int j=1; j<i; j++) f[Now][i]=(f[Now][i]+(f[Now][i-j]*f[Next][j])%mod)%mod; } } bool cmp(const int& a,const int& b) { return Size[a]<Size[b]; } int main() { T=Get_Int(); for(int t=1; t<=T; t++) { n=Get_Int(); Clear(); for(int i=1; i<n; i++) { int x=Get_Int(),y=Get_Int(); AddEdge(x,y); AddEdge(y,x); } Dfs(1,0); if(core1&&core2) { Core=++n; for(int i=0; i<edges[core1].size(); i++) { int& Next=edges[core1][i]; if(Next==core2)Next=Core; } for(int i=0; i<edges[core2].size(); i++) { int& Next=edges[core2][i]; if(Next==core1)Next=Core; } AddEdge(Core,core1); AddEdge(Core,core2); ifunion=1; } else Core=core1; TreeDp(Core,0); for(int i=0; i<edges[Core].size(); i++)son[++tot]=edges[Core][i]; sort(son+1,son+tot+1,cmp); for(int i=0; i<=200; i++)g[0][i][0]=g[0][i][1]=1; for(int i=1; i<=tot; i++) { for(int j=1; j<=Size[son[i]]; j++) for(int k=0; k<=j; k++) for(int t=0; t<=sum; t++) g[i][j][k+t]=(g[i][j][k+t]+f[son[i]][k]*g[i-1][min(j,Size[son[i-1]])][t])%mod; sum+=Size[son[i]]; } for(int i=1; i<=Size[son[tot]]; i++) for(int j=2*i; j<=n; j++) ans=(ans+g[tot][i][j]-g[tot][i-1][j])%mod; printf("Case %d: %d\n",t,((ans-ifunion)%mod+mod)%mod); } return 0; }
|