题目链接

  我貌似又做了一道高精题呢(笑)

  这题的DP方程很好想,设f[i][j]表示i为根的子树,i所在联通块大小为j的最大值,然后乱搞

  但是要高精,那么搞是得要高精除的

  所以考虑f[i][j]是除以j后的最大值,就可以只写高精乘了

  不过卡常,下面代码只能得95分

// luogu-judger-enable-o2
// luogu-judger-enable-o2
#include<cstdio>
#include<iostream>
#include<cctype>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#define maxl 120
#define maxn 702
#define check(x) if(x==0) x=++tot;
using namespace std; inline long long read(){
long long num=,f=;
char ch=getchar();
while(!isdigit(ch)){
if(ch=='-') f=-;
ch=getchar();
}
while(isdigit(ch)){
num=num*+ch-'';
ch=getchar();
}
return num*f;
} struct BigInteger{
int s[maxl],len;
BigInteger(){len=;memset(s,,sizeof(s));}
BigInteger operator =(const char *c){
len=;
for(int i=strlen(c+);i;--i) s[++len]=c[i]-'';
return *this;
}
BigInteger operator =(const int num){
char c[maxl];
sprintf(c+,"%d",num);
(*this)=c;
return *this;
}
BigInteger operator *(BigInteger a){
BigInteger ans;
ans.len=len+a.len;
for(int i=;i<=len;++i)
for(register int j=;j<=a.len;++j)
ans.s[i+j-]+=s[i]*a.s[j];
int g=;
for(int i=;i<=(len+a.len)||g;++i){
ans.s[i]+=g;
g=ans.s[i]/;
ans.s[i]%=;
if(ans.len<i) ans.len=i;
}
while(ans.len&&ans.s[ans.len]==) ans.len--;
return ans;
}
BigInteger operator *(const int a){
BigInteger ans=(*this);
int g=,lim=ans.len;
for(int i=;(i<=lim)||g;++i){
ans.s[i]=ans.s[i]*a+g;
g=ans.s[i]/;
ans.s[i]%=;
if(i>ans.len) ans.len=i;
}
while(ans.len&&ans.s[ans.len]==) ans.len--;
return ans;
}
bool operator <(const BigInteger a)const{
if(len!=a.len) return len<a.len;
for(int i=len;i;--i)
if(s[i]!=a.s[i]) return s[i]<a.s[i];
return ;
}
}; inline void print(BigInteger a){
if(a.len==) putchar('');
for(int i=a.len;i;--i) putchar(a.s[i]+'');
} BigInteger f[maxn*];
int tot;
int size[maxn];
int pos[maxn][maxn];
BigInteger ans; struct Edge{
int next,to;
}edge[maxn*];
int head[maxn],num;
inline void add(int from,int to){
edge[++num]=(Edge){head[from],to};
head[from]=num;
} void dfs(int x,int fa){
check(pos[x][]); check(pos[x][]);
f[pos[x][]]=;f[pos[x][]]=; size[x]=;
for(int i=head[x];i;i=edge[i].next){
int to=edge[i].to;
if(to==fa) continue;
dfs(to,x);
size[x]+=size[to];
for(int j=size[x];j>=;--j){
check(pos[x][j]);
for(int k=min(j,size[x]-size[to]);k>=min(,size[x]-size[to]);--k)
if(f[pos[x][j]]<f[pos[to][j-k]]*f[pos[x][k]]){
f[pos[x][j]]=f[pos[to][j-k]]*f[pos[x][k]];
}
}
}
for(int j=;j<=size[x];++j){
if(f[pos[x][]]<f[pos[x][j]]*j){
f[pos[x][]]=f[pos[x][j]]*j;
if(ans<f[pos[x][]]) ans=f[pos[x][]];
}
}
} int main(){
int n=read();
for(int i=;i<n;++i){
int x=read(),y=read();
add(x,y);
add(y,x);
}
dfs(,);
print(ans);
}

最新文章

  1. MySQL数据库的备份与还原
  2. MODBUS-RTU通讯协议简介
  3. QTabWidget 使用方法
  4. php操作oracle的方法类集全
  5. C++问题-无法打开包括文件:“GLES2/gl2.h”
  6. POJ 2778 DNA sequence
  7. ubuntu 16.04 chrome flash player 过期
  8. ASP.NET 根据现有动态页面生成静态Html
  9. c++在函数后面加const
  10. python 重要模块
  11. Codeforces 241B
  12. tomcat一个端口配置多个项目
  13. [HNOI2002]营业额统计_Treap
  14. WUOJ-ACM :1003: 零起点学算法78——牛牛
  15. SSM-MyBatis-18:Mybatis中二级缓存和第三方Ehcache配置
  16. 怎样在ASP.NET(C#) 使用Json序列化反序列化问题?
  17. [Swift]LeetCode621. 任务调度器 | Task Scheduler
  18. [uva P1601] The Morning after Halloween
  19. django外使用django ORM
  20. j2ee分布式缓存同步实现方案dlcache

热门文章

  1. MovieReview—A dog&#39;s purpose(一只狗的使命)
  2. Lua与游戏的不解之缘
  3. Spark集群任务提交
  4. windbg双机调试配置
  5. 使用struts2实现文件上传与下载功能
  6. Bootstrap 下拉菜单(dropdown)插件
  7. kvm笔记
  8. echarts事件中获取当前实例
  9. A. Vitya in the Countryside
  10. 【Git版本控制】git将单个文件回退到某一版本