FJWC2016 CodeForces 23E 树上游戏 【DP】
考场上鬼畜的把高精度写炸了
Orz,明天就省选了TAT
# include <stdio.h> # include <string.h> # include <stdlib.h> # include <math.h> # include <algorithm> # include <iostream> using namespace std; # define ll long long const ll T=100000000; struct bn { ll t[50]; bn() { memset(t,0,sizeof(t)); t[0]=1; } bn(int x) { memset(t,0,sizeof(t)); t[1]=x,t[0]=1; } ll& operator[](const int i) { return t[i]; } friend bn operator *(bn a,bn b) { bn c; for (int i=1;i<=a[0];++i) for (int j=1;j<=b[0];++j) { c[i+j-1]+=a[i]*b[j]; if(c[i+j-1]>T) { c[i+j]+=c[i+j-1]/T; c[i+j-1]%=T; } } c[0]=a[0]+b[0]; if(c[0]>40) c[0]=40; while(!c[c[0]] && c[0]>0) --c[0]; return c; } friend bool operator>(bn a,bn b) { if(a[0]!=b[0]) return a[0]>b[0]; for (int i=a[0];i>=1;--i) if(a[i]!=b[i]) return a[i]>b[i]; return 0; } void print() { printf("%d",(int)t[t[0]]); for (int i=t[0]-1;i>=1;--i) printf("%08d",(int)t[i]); } }; const int M=710,MM=77100; int n,head[MM],next[MM],to[MM],tot,deg[MM],son[MM]; bn f[M][M]; inline void add(int u,int v) { tot++; next[tot]=head[u]; head[u]=tot; to[tot]=v; } inline void dfs(int x,int fa) { son[x]=1; f[x][1]=1; for (int i=head[x];i;i=next[i]) if(to[i]!=fa) { dfs(to[i],x); for (int j=son[x];j;j--) for (int k=son[to[i]];k>=0;--k) { bn g=f[x][j]*f[to[i]][k]; if(g>f[x][j+k]) f[x][j+k]=g; } son[x]+=son[to[i]]; } f[x][0]=bn(son[x]); for (int i=1;i<=son[x];++i) { bn g=f[x][i]*bn(i); if(g>f[x][0]) f[x][0]=g; } } int main() { int u,v; scanf("%d",&n); for (int i=1;i<=n-1;++i) { scanf("%d%d",&u,&v); add(u,v); add(v,u); } add(n+1,1); dfs(n+1,0); f[1][0].print(); return 0; }