Problem 2 树(tree.cpp/c/pas)
【题目描述】
L发明了一种与树有关的游戏（友情提醒：树是一个没有环的连通图）：他从树中删除任意数量（可以为0）的边，计算删除后所有连通块大小的乘积，L将得到这么多的分数。你的任务就是对于一颗给定的树，求出L能得到的最大分数。
【输入格式】
第一行一个整数n，表示树的节点个数。
接下来n-1行，每行两个整数a[i],b[i](1<=a[i],b[i]<=n)，表示a[i]与b[i]之间连边。
保证输入的图是一棵树。
【输出格式】
输出一个整数，表示L能得到的最大分数。
?【样例输入】
样例1：
5
1 2
2 3
3 4
4 5
样例2：
8
1 2
1 3
2 4
2 5
3 6
3 7
6 8
样例3：
3
1 2
1 3
【样例输出】
样例1：
6
样例2：
18
样例3：
3
【数据范围】
? ? 对于10%的数据，1<=n<=5；
对于30%的数据，1<=n<=100；
另有30%的数据，保证数据是一条链。
对于100%的数据，1<=n<=700；
?
树上背包
f[i][j]表示i的父亲的连通块在子树i中有j个的最大的最大值。
于是这就是树形Dp+背包合并了、
背包合并2个先合并，再与第三个……
[cpp]?
#include ?
#include ?
#include ?
#include ?
#include ?
#include ?
using namespace std; ?
#define MAXN (700+10) ?
#define ll long long ?
#define F (100000000) ?
int n,edge[MAXN*2],pre[MAXN],next[MAXN*2],size=0,son[MAXN]; ?
struct bign ?
{ ?
? ? ll a[40]; ?
? ? bign(){memset(a,0,sizeof(a));a[0]=1;} ?
? ? bign(int x){memset(a,0,sizeof(a)); a[0]=1;a[1]=x; ? } ?
? ? ll& operator[](const int i){return a[i]; ? ?} ?
? ? friend bign operator*(bign a,bign b) ?
? ? { ?
? ? ? ? bign 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]>F) ?
? ? ? ? ? ? ? ? { ?
? ? ? ? ? ? ? ? ? ? c[i+j]+=c[i+j-1]/F; ?
? ? ? ? ? ? ? ? ? ? c[i+j-1]%=F; ?
? ? ? ? ? ? ? ? } ?
? ? ? ? ? ? } ?
? ? ? ? c[0]=min(a[0]+b[0],(long long)39);while (!c[c[0]]&&c[0]>1) c[0]--; ?
? ? ? ? return c; ?
? ? } ??
? ? friend bool operator>(bign a,bign b) ?
? ? { ?
? ? ? ? if (a[0]!=b[0]) return a[0]>b[0]; ?
? ? ? ? for (int i=a[0],j=b[0];i>0;i--,j--) if (a[i]!=b[j]) return a[i]>b[j]; ?
? ? ? ? return false; ? ? ? ??
? ? } ?
? ? void print() ?
? ? { ?
? ? ? ? printf("%I64d",a[a[0]]); ?
? ? ? ? for (int i=a[0]-1;i;i--) ?
? ? ? ? { ?
? ? ? ? ? ? printf("%.8I64d",a[i]); ?
? ? ? ? } ?
? ? } ?
}f[MAXN][MAXN]; ?
bign max(bign a,bign b) ?
{ ?
? ? if (a>b) return a; ?
? ? return b; ?
} ?
void addedge(int u,int v) ?
{ ?
? ? edge[++size]=v; ?
? ? next[size]=pre[u]; ?
? ? pre[u]=size; ?
} ?
void dfs(int x,int father) ?
{ ?
? ? son[x]=1;//f[x][1]=1; ?
? ? f[x][1]=1; ?
? ? for (int p=pre[x];p;p=next[p]) ?
? ? { ?
? ? ? ? int &v=edge[p]; ?
? ? ? ? if (v!=father) ?
? ? ? ? { ?
? ? ? ? ? ? dfs(v,x); ?
? ? ? ? ? ? /*?
? ? ? ? ? ? for (int i=son[x]+son[v];i>0;i--)?
? ? ? ? ? ? {?
? ? ? ? ? ? ? ? if (i
? ? ? ? ? ? ? ? for (int k=son[v];k>=0;k--)?
? ? ? ? ? ? ? ? ? ? if (i-k-1>=0) f[x][i]=max(f[x][i],f[x][i-k-1]*f[v][k]);?
? ? ? ? ? ? ?
? ? ? ? ? ? }?
? ? ? ? ? ? son[x]+=son[v];?
? ? ? ? ? ? bign maxv=son[v];?
? ? ? ? ? ? for (int k=0;k<=son[v]-1;k++) maxv=max(maxv,f[v][k]*(k+1)); ? ? ? ? ? ? ? ? ? ? ??
? ? ? ? ? ? f[x][0]=f[x][0]*maxv;?
? ? ? ? ? ? */ ?
? ? ? ? ? ? for (int i=son[x];i;i--) ?
? ? ? ? ? ? ? ? for (int j=son[v];j>=0;j--) ?
? ? ? ? ? ? ? ? ? ? f[x][i+j]=max(f[x][i+j],f[x][i]*f[v][j]); ? ? ? ? ? ??
? ? ? ? ? ? son[x]+=son[v]; ?
? ? ? ? } ?
? ? } ? ??
? ? f[x][0]=bign(son[x]); ?
? ? for (int i=1;i<=son[x];i++) f[x][0]=max(f[x][0],f[x][i]*bign(i)); ?
? ? ??
? ? ??
? ? ??
? ? ??
? ? return; ?
} ?
int main() ?
{ ?
// ?freopen("tree.in","r",stdin); ?
// ?freopen("tree.out","w",stdout); ?
? ? scanf("%d",&n); ?
? ? memset(pre,0,sizeof(pre)); ?
? ? memset(next,0,sizeof(next)); ?
? ? for (int i=1;i
? ? { ?
? ? ? ? int u,v; ?
? ? ? ? scanf("%d%d",&u,&v); ?
? ? ? ? addedge(u,v);addedge(v,u); ?
? ? } ?
? ? addedge(n+1,1); ?
? ? dfs(n+1,0); //n+1 is ans ?
? ? /*?
? ? for (int i=1;i<=n+1;i++)?
? ? {?
? ? ? ? for (int j=0;j<=son[i]-1;j++)?
? ? ? ? {