洛谷 P1352 没有上司的舞会

// ✗ P1352 第一版：按快乐指数从大到小，能选就选
//
// 大多数人第一眼的想法：谁带来的快乐多就先请谁，只要他的上司和下属都还没请。
// 它给出的**是一个真能办成的名单**（没有任何一对上下级同时在场）
//   ⇒ 所以它恒 ≤ 正解，永远不会「多报」。
// 错在哪：请了一个大的，可能挡住两个更大的（经典的独立集反例：一个 100 卡住两个 90）。

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

const int MAXN = 6005;
int n, r[MAXN];
vector<int> adj[MAXN];      // 无向：上司和下属都算相邻
bool taken[MAXN];

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 >> r[i];
    int l, k;
    while (cin >> l >> k) {
        if (l == 0 && k == 0) break;
        adj[l].push_back(k);
        adj[k].push_back(l);
    }

    vector<int> ord(n);
    for (int i = 0; i < n; i++) ord[i] = i + 1;
    sort(ord.begin(), ord.end(), [](int a, int b) { return r[a] > r[b]; });

    long long sum = 0;
    for (int u : ord) {
        if (r[u] <= 0) continue;            // 负数请来只会更差
        bool blocked = false;
        for (int v : adj[u]) if (taken[v]) { blocked = true; break; }
        if (blocked) continue;
        taken[u] = true;
        sum += r[u];
    }
    cout << sum << '\n';
    return 0;
}

// P1352 没有上司的舞会 —— 正解：树形 DP，O(n)
//
// f[u][0] = u 不来时，u 的子树里最大的快乐指数和
// f[u][1] = u   来时，同上
//   f[u][0] = Σ max(f[v][0], f[v][1])     下属来不来都行，取大的那个
//   f[u][1] = r[u] + Σ f[v][0]            u 来了，下属一个都不能来
// 答案 = max(f[root][0], f[root][1])
//
// ★ 两件和算法无关、却真会挂人的事，都挤在读入这几行里：
//   ① 根要自己找 —— 输入给的是「l 的上司是 k」，从没当过 l 的那个点才是根；
//   ② 读到 (0, 0) 就停 —— 题面写的是 n-1 行，而这道题的数据常被人提到
//      「末尾多一行 0 0」。挡一句一分钱不吃亏；不挡的写法里有一种会自环。

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

const int MAXN = 6005;
int n, r[MAXN], f[MAXN][2];
vector<int> son[MAXN];
bool hasFa[MAXN];

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = r[u];
    for (int v : son[u]) {
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);   // 下属来不来都行
        f[u][1] += f[v][0];                 // 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 >> r[i];

    int l, k;
    while (cin >> l >> k) {
        if (l == 0 && k == 0) break;        // ← ② 挡住那对 (0, 0)
        son[k].push_back(l);
        hasFa[l] = true;
    }

    int root = 1;                           // ← ① 自己找根
    for (int i = 1; i <= n; i++) if (!hasFa[i]) { root = i; break; }

    dfs(root);
    cout << max(f[root][0], f[root][1]) << '\n';
    return 0;
}

// ✗ P1352：把「编号从 0 开始」的习惯带了过来 —— 找根时从 0 号点找起
//
// ⚠ 这个错法有一个非常具体的来处：**同一章题单里的下一道题 [P2016 战略游戏]
//    的结点编号真的是 0 ~ n-1**。先写完那道再回头写这道，很容易顺手写成 `for (i = 0; ...)`。
//
// 后果：0 号点从来没当过谁的下属 ⇒ 它「没有上司」⇒ 被当成根。
// 而 0 号点是个空点（r[0] = 0、没有下属），于是这份程序**恒输出 0**。

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

const int MAXN = 6005;
int n, r[MAXN], f[MAXN][2];
vector<int> son[MAXN];
bool hasFa[MAXN];

void dfs(int u) {
    f[u][0] = 0;
    f[u][1] = r[u];
    for (int v : son[u]) {
        dfs(v);
        f[u][0] += max(f[v][0], f[v][1]);
        f[u][1] += f[v][0];
    }
}

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 >> r[i];
    int l, k;
    while (cin >> l >> k) {
        if (l == 0 && k == 0) break;
        son[k].push_back(l);
        hasFa[l] = true;
    }

    int root = 1;
    for (int i = 0; i <= n; i++) if (!hasFa[i]) { root = i; break; }   // ← 从 0 找起

    dfs(root);
    cout << max(f[root][0], f[root][1]) << '\n';
    return 0;
}