考虑如果子树的和为负，那么删掉它一定比不删掉它更优，用一个cut数组记录这个子树是否删去。注意这题不一定到根节点是最优的，所以要算一个子树更新一次。
代码语言：javascript
复制
//洛谷P1122最大子树和
// 树形dp 简单
//子树计数
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 200005;
struct N{
int v,nxt;
}edge[maxn<<2];
int cnt,ans;
int head[maxn],w[maxn],dp[maxn],cut[maxn];
void add(int u,int v){
cnt++;
edge[cnt].v = v;
edge[cnt].nxt = head[u];
head[u] = cnt;
}
void dfs(int u,int fa)
{
dp[u] = w[u];
for(int v,i=head[u];i;i=edge[i].nxt){
v = edge[i].v;
if(v==fa)continue;
dfs(v,u);
}
for(int v,i=head[u];i;i=edge[i].nxt){//掌握子树所有信息才更新父亲
v = edge[i].v;
if(v!=fa&&(!cut[v])){
dp[u]+=dp[v];
}
}
if(dp[u]<0)cut[u]=1;
ans = max(ans,dp[u]);//不一定根结点最优，算一次更新一次答案
}
int main()
{
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&w[i]);
for(int i=1;i<=n-1;i++){
int u,v;
scanf("%d %d",&u,&v);
add(u,v); add(v,u);
}
dfs(1,0);
printf("%d\n",ans);
return 0;
}