洛谷 P1122 最大子树和

// ✗ P1122 第一版：把所有「美丽指数为正」的花加起来
//
// 想法很顺：负的都剪掉不就完了吗？
// ★ 它错在**连通性**：剪枝只能沿着枝条剪，剩下的必须还是**连在一起的一株**。
//    两朵好花中间隔着一朵烂花，你没法只要两头。
// ⇒ 它解的是一个**放宽了的问题**（不要求连通）⇒ **恒 ≥ 正解**。

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    if (!(cin >> n) || n <= 0) return 0;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; }

    long long sum = 0;
    int mx = INT_MIN;
    for (int i = 1; i <= n; i++) { if (a[i] > 0) sum += a[i]; mx = max(mx, a[i]); }
    if (sum == 0) sum = mx;              // 一朵都没有正的，那就留最好的那一朵
    cout << sum << '\n';
    return 0;
}

// P1122 最大子树和 —— 正解：树形 DP，O(n)
//
//   f[u] = 「必须留下 u」时，u 这一块（在以 u 为根的子树里）能凑出的最大美丽指数和
//        = a[u] + Σ max(0, f[v])
//
// ★ `max(0, f[v])` 这一下就是全部：一个儿子那边算出来是负的，**剪掉它**（题目允许修剪），
//    不亏；是正的就接上。
// ★ 答案是 **max over u of f[u]** —— 不是 f[根]！留下来的那一株可以挂在树的任何地方。
// ⚠ 而它也**不能取 max(0, ...)**：题面说修剪完「还剩下最后一株花（也可能是一朵）」
//    ⇒ 至少要留一朵 ⇒ 美丽指数全是负数时，答案是最大的那个负数，不是 0。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 16005;
int n, a[MAXN];
vector<int> adj[MAXN];
int f[MAXN];
int ans;

void dfs(int u, int fa) {
    f[u] = a[u];
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        if (f[v] > 0) f[u] += f[v];      // 负的那一枝直接剪掉
    }
    ans = max(ans, f[u]);
}

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

    if (!(cin >> n) || n <= 0) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }

    ans = INT_MIN;                       // ← 不能写成 0
    dfs(1, 0);
    cout << ans << '\n';
    return 0;
}

// ✗ P1122：忘了那个 max(0, ·)，儿子那边算出来是负的也照单全收
//
//   f[u] = a[u] + Σ f[v]
//
// ★ 它算了什么：它要求「留下 u 就必须把 u 的整棵子树全留下」——
//    **修剪这个动作被取消了**（只剩「从哪儿把整株砍下来」这一种选择）。
// ⇒ 它解的是一个**收紧了的问题** ⇒ 恒 ≤ 正解。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 16005;
int n, a[MAXN], f[MAXN], ans;
vector<int> adj[MAXN];

void dfs(int u, int fa) {
    f[u] = a[u];
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        f[u] += f[v];                    // ← 少了 max(0, ·)
    }
    ans = max(ans, f[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n) || n <= 0) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); }
    ans = INT_MIN;
    dfs(1, 0);
    cout << ans << '\n';
    return 0;
}

// ✗ P1122：只输出 f[1]，忘了对所有点取 max
//
// ★ 它算了什么：它要求**留下来的那一株必须含 1 号花**。
// ⇒ 又一个收紧了的问题 ⇒ 恒 ≤ 正解。
// ⚠ 而 1 号花是谁完全是随机的 —— 这就是「生成器不打乱编号，就会给某个点安排特殊身份」
//    （第 27 章正文第 ⑫ 步）在这道题上的样子。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 16005;
int n, a[MAXN], f[MAXN];
vector<int> adj[MAXN];

void dfs(int u, int fa) {
    f[u] = a[u];
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        if (f[v] > 0) f[u] += f[v];
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n) || n <= 0) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); }
    dfs(1, 0);
    cout << f[1] << '\n';                // ← 只看了根
    return 0;
}

// ✗ P1122：答案的初值写成了 0（以为「什么都不留」也算一种修剪）
//
// ★ 题面那句「经过一系列修剪之后，**还剩下最后一株花（也可能是一朵）**」是**命门**：
//    至少要留一朵。所以美丽指数全是负数时，答案是**最大的那个负数**，不是 0。
// ⇒ 被抓的轮数 ≡ 全部美丽指数都是负数的轮数 —— 而顺手写的生成器（正负都有）
//    造出这种输入的概率是 2⁻ⁿ ⇒ 在默认档上它是**精确的 0**。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 16005;
int n, a[MAXN], f[MAXN], ans;
vector<int> adj[MAXN];

void dfs(int u, int fa) {
    f[u] = a[u];
    for (int v : adj[u]) {
        if (v == fa) continue;
        dfs(v, u);
        if (f[v] > 0) f[u] += f[v];
    }
    ans = max(ans, f[u]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    if (!(cin >> n) || n <= 0) return 0;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i < n; i++) { int x, y; cin >> x >> y; adj[x].push_back(y); adj[y].push_back(x); }
    ans = 0;                             // ← 这里
    dfs(1, 0);
    cout << ans << '\n';
    return 0;
}