[蓝桥杯 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;
}