FJWC2016 CodeForces 23E 树上游戏 【DP】

tonyfang posted @ 2016年2月20日 22:12 in 随笔 with tags C++ OI , 343 阅读

考场上鬼畜的把高精度写炸了

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;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter