码了一晚上高精度,结果还被卡内存了。。。
比较裸的树形DP,高精度太恶心了。
最后换成JAVA大数,一发过了。
import java.math.BigInteger; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Main { public static BigInteger f[][][]; public static int sz[]; public static List g[]; public static int ed[]; public static void solve (int u,int pre) { sz[u] = 1; int ff = 1; for (int i=0;i<=sz[u];i++) f[0][u][i] = new BigInteger("0"); f[0][u][1] = new BigInteger("1"); for (int k=0;k<g[u].size();k++) { int v = (int) g[u].get(k); if (v == pre) continue; solve(v,u); sz[u]+=sz[v]; for (int i=0;i<=sz[u];i++) f[ff][u][i]=new BigInteger("0"); for (int i=1;i<=sz[u];i++) { for (int j=1;j<=sz[v];j++) { if (j>=i) break; if (i-j>sz[u]-sz[v]) continue; f[ff][u][i]=f[ff][u][i].max(f[ff^1][u][i-j].divide(BigInteger.valueOf(i-j)).multiply(BigInteger.valueOf(i)).multiply(f[ed[v]][v][j]).divide(BigInteger.valueOf(j))); } if (i>sz[u]-sz[v]) continue; for (int j=1;j<=sz[v];j++) { f[ff][u][i]=f[ff][u][i].max(f[ff^1][u][i].multiply(f[ed[v]][v][j])); } } ff^=1; } ed[u]=(ff^1); } public static void main (String []args) { f = new BigInteger[2][705][705]; sz = new int[705]; g = new List[705]; ed = new int[705]; for (int i=0;i<705;i++) g[i] = new ArrayList<Integer>(); Scanner in = new Scanner(System.in); int n=in.nextInt(); for (int i=1;i<n;i++) { int x=in.nextInt(); int y=in.nextInt(); g[x].add(y); g[y].add(x); } solve(1,0); BigInteger ans = new BigInteger("0"); for (int i=1;i<=n;i++) ans=ans.max(f[ed[1]][1][i]); System.out.println(ans); } }