[蓝桥杯 2015 省 B] 生命之树

水一水的入门树形DP

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
using ll = long long;
#define int long long
const int N = 2e6+10;
const int inf = 0x3f3f3f3f;
const int mod = 1e9+7;

int n;
int w[N];
vector<vector<int>>g(N);
int dp[N];
int ans;
void dfs(int u,int fa){
	
	dp[u]+=w[u];
	
	for(auto &t:g[u]){
		if(t==fa)continue;
		dfs(t,u);
		if(dp[t]>0)dp[u]+=dp[t];
	}
	
	ans = max(ans,dp[u]);
	
	
}

void solve()
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>w[i];
	
	for(int i=1;i<n;i++){
		int a,b;cin>>a>>b;
		g[a].push_back(b),g[b].push_back(a);
	}
	
	
	dfs(1,-1);
	cout<<ans;
	
}

signed main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int _;
	//cin>>_;
	_ = 1;
	while(_--)solve();
	return 0;
}