【Luogu】P1411树(树形高精DP)
2024-09-02 02:40:04
我貌似又做了一道高精题呢(笑)
这题的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);
}
最新文章
- MySQL数据库的备份与还原
- MODBUS-RTU通讯协议简介
- QTabWidget 使用方法
- php操作oracle的方法类集全
- C++问题-无法打开包括文件:“GLES2/gl2.h”
- POJ 2778 DNA sequence
- ubuntu 16.04 chrome flash player 过期
- ASP.NET 根据现有动态页面生成静态Html
- c++在函数后面加const
- python 重要模块
- Codeforces 241B
- tomcat一个端口配置多个项目
- [HNOI2002]营业额统计_Treap
- WUOJ-ACM :1003: 零起点学算法78——牛牛
- SSM-MyBatis-18:Mybatis中二级缓存和第三方Ehcache配置
- 怎样在ASP.NET(C#) 使用Json序列化反序列化问题?
- [Swift]LeetCode621. 任务调度器 | Task Scheduler
- [uva P1601] The Morning after Halloween
- django外使用django ORM
- j2ee分布式缓存同步实现方案dlcache