洛谷—— P1122 最大子树和
2024-09-08 16:29:02
https://www.luogu.org/problem/show?pid=1122
题目描述
小明对数学饱有兴趣,并且是个勤奋好学的学生,总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课,路上见到一个老伯正在修剪花花草草,顿时想到了一个有关修剪花卉的问题。于是当日课后,小明就向老师提出了这个问题:
一株奇怪的花卉,上面共连有N 朵花,共有N-1条枝干将花儿连在一起,并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”,该数越大说明这朵花越漂亮,也有“美丽指数”为负数的,说明这朵花看着都让人恶心。所谓“修剪”,意为:去掉其中的一条枝条,这样一株花就成了两株,扔掉其中一株。经过一系列“修剪“之后,还剩下最后一株花(也可能是一朵)。老师的任务就是:通过一系列“修剪”(也可以什么“修剪”都不进行),使剩下的那株(那朵)花卉上所有花朵的“美丽指数”之和最大。
老师想了一会儿,给出了正解。小明见问题被轻易攻破,相当不爽,于是又拿来问你。
输入输出格式
输入格式:
输入文件maxsum3.in的第一行一个整数N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共N 朵花。
第二行有N 个整数,第I个整数表示第I朵花的美丽指数。
接下来N-1行每行两个整数a,b,表示存在一条连接第a 朵花和第b朵花的枝条。
输出格式:
输出文件maxsum3.out仅包括一个数,表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过2147483647。
输入输出样例
输入样例#1:
7
-1 -1 -1 1 1 1 0
1 4
2 5
3 6
4 7
5 7
6 7
输出样例#1:
3
说明
【数据规模与约定】
对于60%的数据,有N≤1000;
对于100%的数据,有N≤16000。
树形DP
任意节点为跟,若他子树和<0,就减去这颗子树,f[u]表示,u的子树的最大和
ans=max{ f[i] }
#include <cstdio> #define max(a,b) (a>b?a:b)
bool if_;
inline void read(int &x)
{
if_=x=; register char ch=getchar();
for(; ch>''||ch<''; ch=getchar()) if(ch=='-') if_=;
for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';
x=if_?((~x)+):x;
}
const int N(+);
int n,val[N],f[N],ans;
int head[N],sumedge;
struct Edge {
int v,next;
Edge(int v=,int next=):v(v),next(next){}
}edge[N<<];
inline void ins(int u,int v)
{
edge[++sumedge]=Edge(v,head[u]);
head[u]=sumedge;
edge[++sumedge]=Edge(u,head[v]);
head[v]=sumedge;
}
int DFS(int u,int fa)
{
if(f[u]) return f[u];
f[u]=val[u];
for(int x,v,i=head[u]; i; i=edge[i].next)
{
v=edge[i].v;
if(v==fa) continue;
x=DFS(v,u); f[u]+=x*(x>);
}
return f[u];
} int Presist()
{
read(n);
for(int i=; i<=n; ++i) read(val[i]);
for(int u,v,i=; i<n; ++i)
read(u),read(v),ins(u,v);
DFS(,-);
for(int i=; i<=n; ++i) ans=max(ans,f[i]);
printf("%d\n",ans);
return ;
} int Aptal=Presist();
int main(){;}
最新文章
- 相克军_Oracle体系_随堂笔记016-参数文件及数据库的启动和关闭
- javac 命令出现 找不到文件 问题及解决办法
- Linux服务器管理: 日志管理(二)
- 项目回顾2-vue的初体验-在已有项目局部使用vue,无须额外配置
- java 14 -5 System类
- Resources in Visual Tracking(转载)
- Android打地鼠游戏源码带道具购买的Android游戏开发
- 20151211Jquery Ajax进阶学习笔记
- PNG在IE6下背景问题
- java 检查是否是数组 检查是否是空数组 检查数组是否包含某个元素
- [转]SGI STL 红黑树(Red-Black Tree)源代码分析
- php 去掉 头尾 空格 2种方法
- Jenkins快速搭建持续集成
- ●洛谷 P3616 富金森林公园
- echart 百度地图实现效果
- git clone 报错
- Docker架构
- 洛谷 P1583魔法照片 &; P1051谁拿了最多奖学金 &; P1093奖学金
- day040 数据库索引补充 存储过程 事务等
- Ubuntu 14.04快速搭建SVN服务器及日常使用