P1122 最大子树和

题目描述小明对数学饱有兴趣并且是个勤奋好学的学生总是在课后留在教室向老师请教一些问题。一天他早晨骑车去上课路上见到一个老伯正在修剪花花草草顿时想到了一个有关修剪花卉的问题。于是当日课后小明就向老师提出了这个问题一株奇怪的花卉上面共连有 n 朵花共有 n−1 条枝干将花儿连在一起并且未修剪时每朵花都不是孤立的。每朵花都有一个“美丽指数”该数越大说明这朵花越漂亮也有“美丽指数”为负数的说明这朵花看着都让人恶心。所谓“修剪”意为去掉其中的一条枝条这样一株花就成了两株扔掉其中一株。经过一系列“修剪“之后还剩下最后一株花也可能是一朵。老师的任务就是通过一系列“修剪”也可以什么“修剪”都不进行使剩下的那株那朵花卉上所有花朵的“美丽指数”之和最大。老师想了一会儿给出了正解。小明见问题被轻易攻破相当不爽于是又拿来问你。输入格式第一行一个整数 n (1≤n≤16000)。表示原始的那株花卉上共 n 朵花。第二行有 n 个整数第 i 个整数表示第 i 朵花的美丽指数。接下来 n−1 行每行两个整数 a,b表示存在一条连接第 a 朵花和第 b 朵花的枝条。输出格式一个数表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超过 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% 的数据有 1≤n≤1000对于 100% 的数据有 1≤n≤16000。这题是个典型树形dp。这题的输入只是输入了两点的连接关系但是他保证了是一整个树。想一下这题思路先遍历到叶子结点在return的时候判断要不要断掉此时数字和上一个数字连接的键如果断掉dp[num]此时这个数字对应的美丽指数如果不断dp[num]dp[儿子]dp[num]所以最后就可以得出:dp[num]max(dp[num],dp[num]dp[儿子]);当然也可以理解为如果儿子是个负数那就不加只有正树才加。AC code#include bits/stdc.h using namespace std; #define int long long const int MAX16005; int a[MAX]; int dp[MAX]; vector long long g[MAX]; void dfs(int num,int fa) { for (int i0;ig[num].size();i) { if (g[num][i]!fa) { dfs(g[num][i],num); dp[num]max(dp[num],dp[num]dp[g[num][i]]); } } return; } signed main () { int n; cinn; for (int i1;in;i) { cina[i]; } int x,y; for (int i1;in;i) { cinxy; g[x].push_back(y); g[y].push_back(x); } for (int i1;in;i) { dp[i]a[i]; } dfs(1,0); int maxx-10086; for (int i1;in;i) { if (maxxdp[i]) { maxxdp[i]; } } if (maxx0) { cout0; } else{ coutmaxx; } return 0; }