<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

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

<|response|>
1. Abridged Problem Statement  
We have an undirected tree of N nodes (towns), each with an integer weight (profit), possibly negative. We must choose a non‐empty connected subset of nodes (i.e. a subtree) so that the sum of the chosen nodes’ weights is as large as possible. Output that maximum sum.

2. Key Observations  
• In a tree, any connected subset of nodes forms a subtree.  
• If a subtree rooted at u contributes a negative total, including it can only lower the overall sum—so we should discard negative contributions.  
• We can root the tree arbitrarily (say at node 0) and do a single depth‐first traversal.  
• Define for each node u a value dp[u] = maximum sum of a connected subtree that (a) contains u and (b) lies entirely in the subtree under u, but we treat negative sums as zero (i.e. dp[u] = max(0, a[u] + sum of positive dp[v] over children v)).  
• While computing dp[u], we also consider the possibility that the optimal subtree ends exactly at u (i.e. uses a[u] + sum of positive child contributions). We keep a global variable ans that tracks the maximum over all such values.

3. Full Solution Approach  
1. Read N and the array of profits a[0…N−1].  
2. Build an adjacency list for the tree from the N−1 edges (convert to 0-based).  
3. Initialize a global variable ans to a very small number (e.g. −∞ or INT_MIN).  
4. Define a recursive DFS(u, parent):  
   a. Initialize subtotal = 0.  
   b. For each neighbor v of u that is not equal to parent, call childSum = DFS(v, u) and add max(childSum, 0) to subtotal.  
   c. Compute currentSum = a[u] + subtotal.  
   d. Update ans = max(ans, currentSum).  
   e. Return max(0, currentSum) to the parent.  
5. Call DFS(0, −1) to traverse the entire tree.  
6. Print ans.  

Time Complexity: O(N) (each node and edge is visited once)  
Memory: O(N) for adjacency lists and DP recursion stack.

4. C++ Implementation with Detailed Comments  
```cpp
#include <bits/stdc++.h>
using namespace std;

int N;
vector<int> profit;
vector<vector<int>> adj;
int globalMax;  // will hold the answer

// DFS returns the maximum sum of a connected subtree
// that includes node u and lies in u's subtree.
// Negative sums are cut to zero.
int dfs(int u, int parent) {
    int subtotal = 0;
    for (int v : adj[u]) {
        if (v == parent) continue;
        int childContribution = dfs(v, u);
        // we only take positive contributions
        if (childContribution > 0)
            subtotal += childContribution;
    }
    int currentSum = profit[u] + subtotal;
    // update the global maximum answer
    globalMax = max(globalMax, currentSum);
    // return non-negative value for parent's consideration
    return max(0, currentSum);
}

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

    // 1. Read input
    cin >> N;
    profit.resize(N);
    for (int i = 0; i < N; i++) {
        cin >> profit[i];
    }
    adj.assign(N, vector<int>());

    // 2. Read edges and build adjacency list (0-based indexing)
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 3. Initialize answer to very small
    globalMax = numeric_limits<int>::min();

    // 4. Run DFS from node 0
    dfs(0, -1);

    // 5. Output the maximum profit
    cout << globalMax << "\n";
    return 0;
}
```

5. Python Implementation with Detailed Comments  
```python
import sys
sys.setrecursionlimit(1000000)

def main():
    data = sys.stdin.read().split()
    it = iter(data)
    # 1. Read number of towns
    n = int(next(it))
    # 2. Read profits
    profit = [int(next(it)) for _ in range(n)]
    # 3. 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)

    # 4. Global variable for the best answer
    best = -10**18

    # 5. DFS function returns max subtree sum rooted at u (non-negative)
    def dfs(u, parent):
        nonlocal best
        subtotal = 0
        for v in adj[u]:
            if v == parent:
                continue
            contrib = dfs(v, u)
            if contrib > 0:
                subtotal += contrib
        current = profit[u] + subtotal
        # update global best
        if current > best:
            best = current
        # return non-negative for upper levels
        return current if current > 0 else 0

    # 6. Trigger DFS from node 0
    dfs(0, -1)
    # 7. Print the result
    print(best)

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