luogu P1122 WA

// Problem: P1122 最大子树和
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1122
// Memory Limit: 128 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template <typename... Args> void logger(string vars, Args &&... values)
{
    cerr << vars << " = ";
    string delim = "";
    (..., (cerr << delim << values, delim = ", "));
    cerr << endl;
}

template <class T> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m)); }
template <class T> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n)); }
template <class T, T init> inline auto vv(int m) { return vector<vector<T>>(m, vector<T>(m, init)); }
template <class T, T init> inline auto vv(int m, int n) { return vector<vector<T>>(m, vector<T>(n, init)); }

template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vl = vector<ll>;
using vi = vector<int>;

vi g[200003];
ll p[200003];
ll ans, tot;
int n;

pll dfs(int u, int fa)
{
    ll take = p[u], no_take = 0;
    for (auto v : g[u]) {
        if (v == fa)
            continue;

        auto [st, snt] = dfs(v, u);

        take += max(st, 0ll);
        no_take = max({no_take, st, snt});
    }
    ans = max({ans, take, no_take});
    return {take, no_take};
}

int main(int argc, char **argv)
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
        cin >> p[i], tot += p[i];
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b), g[b].push_back(a);
    }

    ans = LLONG_MIN;
    dfs(1, -1);
    cout << ans << endl;
    return 0;
};