# 题目大意
真讨厌题面写的老长老长的。
这个题的意思就是给定一棵无根树，每个节点都有一个美丽值（可能是负数），可以删掉一些边来删除某些点，现在要求你求出可以删掉任意条边的情况下，这个树上的剩余节点的美丽值之和的最大值。
# 解题思路
以每一个节点为根，做 $\text{dfs}$，考虑到这样的一个性质，如果一棵子树节点的美丽值之和为负数，那就可以将这棵子树全部删掉。
所以就在 $\text{dfs}$ 的同时记录一下子树的美丽值之和。如果你这样做的话，会得到 $70$ 分的好成绩（会 $\text{TLE}$ 三个点）。所以要加入记忆化，应该没什么难的，这样子来看的话，这其实是一道树形 $\text{DP}$ 的入门级题目。不过懒得改了，就交记忆化的版本吧。
# 附上代码
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn =
16003;
int n, a[maxn], rt, head[maxn], cnt, ans, num[maxn];
struct edge {
int nxt, u, v;
}ed[maxn <<
1];
inline void addedge(
int x,
int y) {
ed[++cnt].nxt =
head[x];
head[x] =
cnt;
ed[cnt].u = x, ed[cnt].v =
y;
}
inline int dfs(
int x,
int fr) {
if(num[x])
return num[x]>
0?num[x]:
0;
num[x] =
a[x];
for(
int i=head[x]; i; i=
ed[i].nxt) {
if(ed[i].v == fr)
continue;
num[x] +=
dfs(ed[i].v, x);
}
if(num[x] <
0)
return 0;
return num[x];
}
int main() {
scanf("%d", &
n);
for(
int i=
1; i<=n; i++) scanf(
"%d", &
a[i]);
int x, y;
for(
int i=
1; i<n; i++
) {
scanf("%d%d", &x, &
y);
addedge(x, y);
addedge(y, x);
}
for(
int i=
1; i<=n; i++
) {
ans = max(ans, dfs(i,
0));
}
printf("%d", ans);
}
转载于:https://www.cnblogs.com/bljfy/p/9628908.html
