Time Limit: 1 second

Memory Limit: 128 MB

【问题描述】

小明对数学饱有兴趣,并且是个勤奋好学的学生,总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课,路上见到一个老伯正在修

剪花花草草,顿时想到了一个有关修剪花卉的问题。于是当日课后,小明就向老师提出了这个问题:

一株奇怪的花卉,上面共连有N 朵花,共有N-1条枝干将花儿连在一起,并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”,该

数越大说明这朵花越漂亮,也有“美丽指数”为负数的,说明这朵花看着都让人恶心。所谓“修剪”,意为:去掉其中的一条枝条,这样一

株花就成了两株,扔掉其中一株。经过一系列“修剪“之后,还剩下最后一株花(也可能是一朵)。老师的任务就是:通过一系列“修剪”

(也可以什么“修剪”都不进行),使剩下的那株(那朵)花卉上所有花朵的“美丽指数”之和最大。

老师想了一会儿,给出了正解。小明见问题被轻易攻破,相当不爽,于是又拿来问你。

【输入格式】

输入文件maxsum3.in的第一行一个整数N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共N 朵花。 第二行有N 个整数,第I个整数表示第I朵花的美丽指数。 接下来N-1行每行两个整数a,b,表示存在一条连接第a 朵花和第b朵花的枝条。

【输出格式】

输出文件maxsum3.out仅包括一个数,表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过2147483647。

【数据规模】

对于60%的数据,有N≤1000; 对于100%的数据,有N≤16000。

Sample Input1

5 7

-1 -1 -1 1 1 1 0

1 4

2 5

3 6

4 7

5 7

6 7

Sample Output1

3

【题目链接】:http://noi.qz5z.com/viewtask.asp?id=u125

【题解】



设f[i]为以i号节点为根的子树的最大子树和(一定包括i号节点);

f[i] = a[i]+∑f[j] (j为i号节点的儿子节点,且f[j]>0);如果f[j]<0就不接上去相当于剪掉;

显然如果儿子节点的最大子树和大于0,则再接到i号节点上肯定能让答案更优。并且如果不和那些直系儿子节点链接,直系儿子节点下面的节点肯定没办法和i号节点相连;因此只有“选择和直系儿子链接”和“不与直系儿子链接”两种选择;而我们的儿子节点的f值已经算出来了;所以能直接加上;

最后在f[i](1<=i<=n中取最大值就好;



【完整代码】

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <set>
#include <map>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <string>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second typedef pair<int,int> pii;
typedef pair<LL,LL> pll; void rel(LL &r)
{
r = 0;
char t = getchar();
while (!isdigit(t) && t!='-') t = getchar();
LL sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
} void rei(int &r)
{
r = 0;
char t = getchar();
while (!isdigit(t)&&t!='-') t = getchar();
int sign = 1;
if (t == '-')sign = -1;
while (!isdigit(t)) t = getchar();
while (isdigit(t)) r = r * 10 + t - '0', t = getchar();
r = r*sign;
} const int MAXN = 16e3+100;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0); int n;
int a[MAXN],f[MAXN];
vector <int> g[MAXN]; void dfs(int x,int fa)
{
int len = g[x].size();
int temp = 0;
rep1(i,0,len-1)
{
int y = g[x][i];
if (y==fa) continue;
dfs(y,x);
temp = max(temp,temp+f[y]);
}
f[x] = max(a[x],temp+a[x]);
} int main()
{
//freopen("F:\\rush.txt","r",stdin);
rei(n);
rep1(i,1,n)
rei(a[i]),f[i] = a[i];
rep1(i,1,n-1)
{
int x,y;
rei(x);rei(y);
g[x].pb(y);
g[y].pb(x);
}
dfs(1,-1);
int ans = f[1];
rep1(i,2,n)
ans = max(ans,f[i]);
printf("%d\n",ans);
return 0;
}

最新文章

  1. react+redux官方实例TODO从最简单的入门(3)-- 删
  2. ibatis.net 中SqlMaps的xml文件的例子
  3. ubtuntu 下安装Erlang R17
  4. iphone 开源汇总(转)
  5. 36 网络相关函数(四)——live555源码阅读(四)网络
  6. hadoop Error: JAVA_HOME is not set and could not be found.
  7. 一加3,CM13蓝牙共享互联网 无效。
  8. 以一个权限系统来告别WebForm —(一)项目整休架构设计与数据库设计
  9. AspectJ AOP学习基础
  10. AI中去掉页面边框
  11. 在线最优化求解(Online Optimization)之三:FOBOS
  12. win10清理C盘
  13. BestCoder Round #36 [B] Gunner
  14. OpenStack云平台的网络模式及其工作机制
  15. Qt-不调用CoInitialize-实现SDL多线程运行
  16. SoapUI之http接口测试
  17. 简单理解php深复制浅复制问题
  18. 五大常用算法之二:动态规划算法(DP)
  19. [Android] AndroidStudio + JNI(NDK)开发相关总结
  20. Css学习(三)

热门文章

  1. [React] Use the URL as the source of truth in React
  2. js---25桥模式
  3. BZOJ1212: [HNOI2004]L语言(Trie图+DP)
  4. bzoj3786星系探索(splay维护dfs序)
  5. MySQL主从同步配置(详细图解)
  6. Scala——构造函数
  7. 【Educational Codeforces Round 35 C】Two Cakes
  8. 【习题 7-3 UVA - 211】The Domino Effect
  9. Android RecyclerView And CardView
  10. Windows环境下ARM集成开发环境的搭建与使用