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<cstdio> #include<cstring> #include<algorithm> #include<functional> #include<iostream> #include<cstdlib> #include<cmath> 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<son[x]) f[x][i]=f[x][i]*son[v]; 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<n;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++) { f[i][j].print();printf(" "); } printf("\n"); } */ // f[n+1][1]=bign(123456789)*bign(234567899); f[1][0].print(); printf("\n"); return 0; }
