前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >洛谷P1122最大子树和 树形结构计算子树和

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

作者头像
用户2965768
发布2019-07-11 10:38:54
4430
发布2019-07-11 10:38:54
举报
文章被收录于专栏:wym

 考虑如果子树的和为负,那么删掉它一定比不删掉它更优,用一个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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年07月10日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档