洛谷P1122最大子树和 树形结构计算子树和

 考虑如果子树的和为负，那么删掉它一定比不删掉它更优，用一个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("%dn",ans); 
	return 0;
}

cut 数组

0 人点赞