动态规划

#include <iostream>
#include <set>
#include <algorithm>
#include <string.h>

using namespace std;
const int N = 20005;
const int inf = 0x3f3f3f3f;
int n, m, head[N], cnt,dp[N],vis[N];
struct 
{
	int next, v;
}node[N<<1];
int res=0;
void add(int u,int v)
{
	node[++cnt].next = head[u];
	node[cnt].v = v;
	head[u] = cnt;
}
void dfs(int u)
{
	vis[u]=1;
	for (int i = head[u]; i;i=node[i].next)
	{
		int v = node[i].v;
		if(vis[v]) continue;
		dfs(v);
		dp[u] += max(dp[v], 0);
	}
	res=max(res,dp[u]);
}
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n;i++)
	{
		cin >> dp[i];
	}
	for (int i = 1; i <= n - 1;i++)
	{
		int a, b;
		cin>>a>>b;
		add(a, b);
		add(b, a);
	}
	dfs(1);
	cout << res << endl;
}