1. Abridged Problem Statement
Given a tree of N towns (nodes) where each town i has an integer profit a[i], find a non-empty connected subtree whose sum of profits is maximal. Output that maximum sum.

2. Detailed Editorial

Problem restatement in your own words
We have an undirected acyclic connected graph (a tree) of N nodes. Each node carries an integer weight (profit), possibly negative. We want to choose a set of nodes that (a) induces a connected subgraph and (b) maximizes the sum of their weights. The chosen subset cannot be empty.

Key observations and approach
- Because the graph is a tree, any connected subset is itself a tree.
- A standard tree‐DP (depth‐first search) computes for each node u the maximum sum of a connected subtree that (i) contains u and (ii) lies entirely in u’s descendants plus u itself.
- If some child’s contribution is negative, it only drags down the sum; so we drop it (treat as zero).

Define a DFS function that returns to its parent: best[u] = max(0, a[u] + Σ best[v] for v a child of u). Meanwhile, we keep a global answer variable ans, updated at each node by ans = max(ans, a[u] + Σ best[v]).

Algorithm steps
1. Read N and the array a[0..N−1] of profits.
2. Build adjacency lists for the tree.
3. Initialize global ans = −∞.
4. Run DFS from an arbitrary root (e.g. node 0), passing parent = −1.
   - For each neighbor v ≠ parent, recurse and get child_contrib = DFS(v,u).
   - Accumulate S = Σ child_contrib (each contribution already clamped at 0).
   - Update ans = max(ans, a[u] + S).
   - Return max(0, a[u] + S) to the parent.
5. Print ans.

Time and memory complexity
- DFS visits each node once and scans its adjacency list, so O(N).
- Memory O(N) for storing weights and adjacency lists.
- N ≤ 16000, fits easily within limits.

3. C++ Solution
```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;
}
```

4. Python Solution with Detailed Comments
```python
import sys
sys.setrecursionlimit(1000000)

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    n = int(next(it))
    # Read profits
    a = [int(next(it)) for _ in range(n)]
    # Build adjacency list
    adj = [[] for _ in range(n)]
    for _ in range(n - 1):
        u = int(next(it)) - 1
        v = int(next(it)) - 1
        adj[u].append(v)
        adj[v].append(u)

    # Global variable to store the best answer
    ans = -10**18

    # DFS returns best sum of a connected subtree rooted at u
    def dfs(u, parent):
        nonlocal ans
        subtotal = 0
        # Visit children
        for v in adj[u]:
            if v == parent:
                continue
            contrib = dfs(v, u)
            # Only add positive contributions
            if contrib > 0:
                subtotal += contrib
        current = subtotal + a[u]
        # Update global maximum
        ans = max(ans, current)
        # Return zero if negative, to prune bad branches
        return current if current > 0 else 0

    # Run DFS from node 0
    dfs(0, -1)
    # Print the result
    print(ans)

if __name__ == "__main__":
    main()
```

5. Compressed Editorial
Compute via one DFS a DP value dp[u] = max(0, a[u] + Σ dp[v] for v children of u). Track a global `ans` = max(ans, a[u] + Σ dp[v]). This yields the maximum sum over all connected subtrees in O(N) time and O(N) memory.
