p143.ans1
======================
4

=================
p143.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream &out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream &in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream &in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream &out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n;
vector<int> a;
vector<vector<int>> adj;

void read() {
    cin >> n;
    a.resize(n);
    cin >> a;
    adj.assign(n, vector<int>());
    for(int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}

int dfs(int u, int p, int& ans) {
    int res = 0;
    for(int v: adj[u]) {
        if(v == p) {
            continue;
        }
        res += dfs(v, u, ans);
    }

    ans = max(ans, res + a[u]);
    return max(0, res + a[u]);
}

void solve() {
    // We want the maximum-profit connected subtree of a tree (the towns form
    // a tree since there is exactly one path between any two). Root anywhere
    // and run a DFS that returns, for each node, the best profit of a
    // connected piece hanging from that node and reaching up into its parent;
    // a child only contributes when its own best is positive (clamped to 0).
    // The best subtree rooted exactly at a node is its own profit plus the
    // sum of positive child contributions, and the global answer is the
    // maximum of that quantity over all nodes.

    int ans = INT_MIN;
    dfs(0, -1, ans);
    cout << ans << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p143.in1
======================
5
-1 1 3 1 -1
4 1
1 3
1 2
4 5

=================
statement.txt
======================
143. Long Live the Queen

time limit per test: 0.25 sec.
memory limit per test: 4096 KB


The Queen of Byteland is very loved by her people. In order to show her their love, the Bytelanders have decided to conquer a new country which will be named according to the queen's name. This new country contains N towns. The towns are connected by bidirectional roads and there is exactly ONE path between any two towns, walking on the country's roads. For each town, the profit it brings to the owner is known. Although the Bytelanders love their queen very much, they don't want to conquer all the N towns for her. They will be satisfied with a non-empty subset of these towns, with the following 2 properties: there exists a path from every town in the subset to every other town in the subset walking only through towns in the subset and the profit of the subset is maximum. The profit of a subset of the N towns is equal to the sum of the profits of the towns which belong to the subset. Your task is to find the maximum profit the Bytelanders may get.


Input

The first line of input will contain the number of towns N (1<=N<=16 000). The second line will contain N integers: the profits for each town, from 1 to N. Each profit is an integer number between -1000 and 1000. The next N-1 lines describe the roads: each line contains 2 integer numbers a and b, separated by blanks, denoting two different towns between which there exists a road.


Output

The output should contain one integer number: the maximum profit the Bytelanders may get.


Sample Input

5
-1 1 3 1 -1
4 1
1 3
1 2
4 5
Sample Output

4
Author	: Mugurel Ionut Andreica
Resource	: SSU::Online Contester Fall Contest #2
Date	: Fall 2002

=================
