http://codeforces.com/problemset/problem/23/E

题意:给一个树,求砍断某些边,使得所有联通块大小的乘积最大。
思路:f[i][j]代表当前把j个贡献给i的父亲(也就是不计入f[i][j])的最大乘积是多少,转移就是背包转移

记得最后统计答案的时候是f[i][j]*j

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define wk sb
#define ll long long
int tot,son[],first[],next[],go[];
int n;
struct node{
int a[],n;
}f[][];
int read(){
int t=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (''<=ch&&ch<=''){t=t*+ch-'';ch=getchar();}
return t*f;
}
void insert(int x,int y){
tot++;
go[tot]=y;
next[tot]=first[x];
first[x]=tot;
}
void add(int x,int y){
insert(x,y);insert(y,x);
}
node operator *(node a,node b){
node c;c.n=;for (int i=;i<=;i++) c.a[i]=;
c.n=a.n+b.n;
for (int i=;i<=a.n;i++)
for (int j=;j<=b.n;j++){
c.a[i+j-]+=a.a[i]*b.a[j];
c.a[i+j]+=c.a[i+j-]/;
c.a[i+j-]%=;
}
int j=;
while (j<=c.n||c.a[j]>){
c.a[j+]+=c.a[j]/;
c.a[j]%=;
j++;
}
while (j>&&c.a[j]==) j--;
c.n=j;
return c;
}
node make(int x){
node c;
c.n=;for (int i=;i<=;i++) c.a[i]=;
while (x){
c.a[++c.n]=x%;
x/=;
}
return c;
}
node up(node a,node b){
if (a.n>b.n) return a;
if (b.n>a.n) return b;
for (int i=a.n;i>=;i--)
if (a.a[i]>b.a[i]) return a;
else
if (b.a[i]>a.a[i]) return b;
return a;
}
void dfs(int x,int fa){
f[x][]=make();
son[x]=;
for (int i=first[x];i;i=next[i]){
int pur=go[i];
if (pur==fa) continue;
dfs(pur,x);
for (int j=son[x];j>=;j--)
for (int k=son[pur];k>=;k--)
f[x][j+k]=up(f[x][j+k],f[x][j]*f[pur][k]);
son[x]+=son[pur];
}
f[x][]=make();
for (int i=;i<=son[x];i++)
f[x][]=up(f[x][],f[x][i]*make(i));
}
int main(){
n=read();
for (int i=;i<n;i++){
int x=read(),y=read();
add(x,y);
}
dfs(,);
printf("%d",(int)f[][].a[f[][].n]);
for (int i=f[][].n-;i>=;i--)
printf("%.4d",(int)f[][].a[i]);
}

最新文章

  1. T-SQL语句简易入门(第一课)
  2. netbean快捷键
  3. spring事务与消息队列
  4. Linux第八次学习笔记
  5. Java Web中将oracle的数据库内容以表格形式展现到页面中(分页展示)
  6. Symantec更新服务器
  7. 【NOIP模拟赛】工资
  8. shu_1241 邮局位置问题
  9. HopSpot虚拟机中的Mark word的作用
  10. java并发包分析之———BlockingQueue
  11. #0 scrapy爬虫学习中遇到的坑记录
  12. KMP性质小结
  13. CentOS7中PPTP的配置
  14. ASP.NET MVC 3 Application Upgrader
  15. web前端中navigator
  16. Linux - history命令的常用方法
  17. PAT 1008 数组元素循环右移问题
  18. 鼠标 DPI与CPI
  19. 这本小书的目的是引导你进入 React 和 Webpack 的世界。他们两个都是非常有用的技术,如果同时使用他们,前端开发会更加有趣。
  20. 23种经典设计模式UML类图汇总

热门文章

  1. C#中DataTable行转列示例
  2. Python之路【第一篇】:Python前世今生
  3. SpringMVC框架图解析
  4. 装多版本号sqlserver的远程连接问题
  5. 20M宽带的网速等价于多少?
  6. 二叉树(二叉链表实现)JAVA代码
  7. #include&lt;iostream.h&gt;与#include&lt;iostream&gt; using namespace std的区别
  8. 30款jQuery常用网页焦点图banner图片切换 下载 (转)
  9. (转)安装 Apache 出现 &lt;OS 10013&gt; 以一种访问权限不允许的方式做了一个访问套接字的尝试
  10. asp.net 定时器