蓝桥杯2015年第六届真题-生命之树

解题思路:树形dp，查找最大子树和

注意事项:集合可以为空,也就是说如果树中节点全小于0则为空集输出0

参考代码:

#include<bits/stdc++.h>
using namespace std;
struct node
{
	int to;
	int w;
	int next;
}mp[1000005];
int head[500005];
int cnt=0;
//int a[100005];
void add(int a,int b)
{
	mp[++cnt].next=head[a];
	mp[cnt].to=b;
	head[a]=cnt;
}
long long dp[500005];
void dfs(int u,int fa)
{
	for(int i=head[u];i;i=mp[i].next)
	{
		int v;
		v=mp[i].to;
		if(v==fa)continue;
		dfs(v,u);		
	}
	dp[fa]=max(dp[fa],dp[u]+dp[fa]);
}
int main()
{
	int n;
	cin>>n;
	int num;
	for(int i=1;i<=n;i++)
	{
		cin>>dp[i];
	}
	for(int i=1;i<n;i++)
	{
		int a,b,c;
		cin>>a>>b;
		add(a,b);
		add(b,a);
	}
	dfs(1,0);
	long long ans=-2147483647;
	for(int i=1;i<=n;i++)
	{
		ans=max(dp[i],ans);
	}
	if(ans<0)ans=0;
	printf("%lld",ans);
}