题目描述
算法1
C++ 代码
#include <bits/stdc++.h>
using namespace std;
#define inf -0x3fffffff
using ll = long long;
const int MN = 1E5 + 6;
ll n, sc[MN];
vector<int> E[MN];
ll f[MN];
void dfs(int x, int p){
//第一个结点的价值
f[x] = sc[x];
for(const auto &u : E[x]){
if(u == p) continue;
dfs(u, x);
f[x] += max(0ll, f[u]);
}
}
int main(){
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(int i = 1; i <= n; ++ i) cin >> sc[i];
for(int i = 1; i < n; ++ i){
int u, v; cin >> u >> v;
E[u].push_back(v);
E[v].push_back(u);
}
dfs(1, 0);
ll ans = inf;
for(int i = 1; i <= n; ++ i)
ans = max(ans, f[i]);
cout << ans;
return 0;
}
fx的0ll用于判断底部叶子结点是否为负