简单 DP，但是毒瘤。开高精还卡空间。。
树形 DP。只关心根节点所处连通块大小，自然记 $f_{i,j}$ 表示以 $i$ 为根的子树中和 $i$ 联通的 $j$ 个点的贡献还没有被计算的答案。这里没有被计算的意思是实际的值为 $j\times f_{i,j}$，只计算了其他连通块的贡献。转移类似树形背包，两种情况：断 $(i,to)$ 边和保留。
断边的转移方程为：
\[f_{i,j}=\max_{k=1}^{siz_{to}}\{f_{i,j}\times kf_{to,k}\}\]保留边的转移方程为：
\[f_{i,j}=\max_{k=1}^{siz_i}\{f_{i,k}\times f_{to,j-k}\}\]最后答案即为 $\max_{k=1}^{n}{k\times f_{1,k}}$
要开高精，支持高精乘高低精和比较大小，复杂度应当是大常数（因为高精） $\mathcal O(n^2)$，跑的飞快。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
int cnt,n,siz[710],head[710],to[1410],nex[1410];
inline void add(int x,int y){to[++cnt]=y,nex[cnt]=head[x],head[x]=cnt;}
namespace BigNum
{
struct Node{short len,a[121];Node(){len=0,memset(a,0,sizeof(a));}}f[701][701],tmp[710],ans;
Node max(Node nd1,Node nd2)
{
if(nd1.len>nd2.len)return nd1;
if(nd1.len<nd2.len)return nd2;
for(int i=nd1.len;i>=1;--i)
{
if(nd1.a[i]>nd2.a[i])return nd1;
if(nd1.a[i]<nd2.a[i])return nd2;
}
return nd1;
}
Node operator *(const Node nd1,const int k)
{
Node nd3;nd3.len=nd1.len;
for(int i=1;i<=nd1.len;++i)nd3.a[i]=nd1.a[i]*k;
for(int i=1;i<=nd1.len;++i)nd3.a[i+1]+=nd3.a[i]/10,nd3.a[i]%=10;
while(nd3.a[nd3.len+1])++nd3.len,nd3.a[nd3.len+1]+=nd3.a[nd3.len]/10,nd3.a[nd3.len]%=10;
return nd3;
}
Node operator *(const Node nd1,const Node nd2)
{
Node nd3;nd3.len=nd1.len+nd2.len-1;
for(int i=1;i<=nd1.len;++i)
{
for(int j=1;j<=nd2.len;++j)
nd3.a[i+j-1]+=nd1.a[i]*nd2.a[j];
}
for(int i=1;i<=nd3.len;++i)nd3.a[i+1]+=nd3.a[i]/10,nd3.a[i]%=10;
while(nd3.a[nd3.len+1])++nd3.len,nd3.a[nd3.len+1]+=nd3.a[nd3.len]/10,nd3.a[nd3.len]%=10;
return nd3;
}
}
using namespace BigNum;
void dfs(int x,int fa)
{
siz[x]=1;f[x][1].a[f[x][1].len=1]=1;
for(int i=head[x];i;i=nex[i])
{
if(to[i]==fa)continue;
dfs(to[i],x);
memcpy(tmp,f[x],sizeof(tmp));
Node maxn;
for(int k=1;k<=siz[to[i]];++k)
maxn=max(maxn,f[to[i]][k]*k);
for(int j=1;j<=siz[x];++j)
{
for(int k=1;k<=siz[to[i]];++k)
f[x][j+k]=max(f[x][j+k],tmp[j]*f[to[i]][k]);
f[x][j]=max(f[x][j],tmp[j]*maxn);
}
siz[x]+=siz[to[i]];
}
}
inline void mian()
{
read(n);int x,y;
for(int i=1;i<n;++i)read(x,y),add(x,y),add(y,x);
dfs(1,0);
for(int i=1;i<=n;++i)
ans=max(ans,f[1][i]*i);
for(int i=ans.len;i>=1;--i)write(ans.a[i],'~');
}