We are given a tree of (n) nodes, each carrying an integer weight (which may be negative). The task is to select a connected subgraph that forms a subtree and maximise the sum of the node weights inside it. The problem appears with two common variants: one that allows an empty selection (answer at least 0) and one that requires at least one node.

Let (dp[u]) denote the maximum sum achievable by a subtree rooted at (u). The recurrence is straightforward: the subtree rooted at (u) must include (u) itself; then it may optionally attach any of the child subtrees that contribute a positive amount. Formally,

[dp[u] = w[u] + \sum_{v \in children(u)} \max(dp[v], 0)]

After computing (dp) for all nodes via a post‑order traversal, the final answer is:

• if the empty set is forbidden: (\max_{i=1..n} dp[i])
• if the empty set is allowed: (\max (0, \max_{i=1..n} dp[i]))

We use an adjacency list to model the tree and run a depth‑first search while tracking the parent to avoid back‑edges. The implementation below uses a function that returns the subtree sum and simultaneously populates an array that records the best value for each root.

Variant 1 – empty set allowed (e.g., Lanqiao Cup P8625)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 100005;
vector<int> tr[N];
long long val[N], best[N];
int n;

long long solve(int u, int p) {
    long long cur = val[u];
    for (int v : tr[u]) {
        if (v == p) continue;
        long long child = solve(v, u);
        if (child > 0) cur += child;
    }
    best[u] = cur;
    return cur;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> val[i];
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        tr[a].push_back(b);
        tr[b].push_back(a);
    }
    solve(1, 0);
    long long ans = 0;
    for (int i = 1; i <= n; ++i)
        ans = max(ans, best[i]);
    cout << ans << '\n';
    return 0;
}

Variant 2 – empty set forbidden (e.g., Luogu P1122 maximum subtree sum)

The recurrence is identical. The only change is that the answer must be a genuine subtree, so we initialise ans with best[1] and then scan all nodes.

// The tree DP part stays the same as above.
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> val[i];
    for (int i = 1; i < n; ++i) {
        int a, b;
        cin >> a >> b;
        tr[a].push_back(b);
        tr[b].push_back(a);
    }
    solve(1, 0);
    long long ans = best[1];
    for (int i = 2; i <= n; ++i)
        if (best[i] > ans) ans = best[i];
    cout << ans << '\n';
    return 0;
}

The algorithm runs in (O(n)) time and (O(n)) space. The two variants illustrate how a small difference in the problem statement (whether an empty selection is permitted) affects only the post‑processing of the (dp) table.