「一本通 5.2 练习 3」周年纪念晚会

题目描述

学校职员构成一棵以校长为根的人事关系树，编号 $1..N$ ，第 $i$ 人有欢乐度 $p_i$ 。要求选出一份名单，使任意一人与其直接上司不同时参加，求总欢乐度最大值。输入第一行为 $N$ ，随后 $N$ 行每行一个 $p_i$ ，接着每行 L K 表示 $K$ 是 $L$ 的直接上司、以 0 0 结束；输出最大欢乐度。样例输入 7 / 1 / 1 / 1 / 1 / 1 / 1 / 1 / 1 3 / 2 3 / 6 4 / 7 4 / 4 5 / 3 5 / 0 0，输出 5。数据范围 $1 \leqslant N \leqslant 6000$ ， $-128 \leqslant p_i \leqslant 127$ 。

思路

树形 DP：每个节点保留两个值，dp0[u] 为 $u$ 不参加时子树的最大欢乐度，dp1[u] 为 $u$ 参加时的值，转移为 dp0[u]=Σmax(dp0[v],dp1[v])、dp1[u]=p[u]+Σdp0[v]（ $v$ 是 $u$ 的直接下属）。按后序（孩子先于父亲）合并，链深可达 6000，用迭代后序避免递归爆栈，答案为 max(dp0[root], dp1[root])。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 20:01
# update_at: 2026-09-30 20:01

import sys
from collections import defaultdict


def tree_dp(children: dict[int, list[int]], joy: list[int], root: int) -> int:
    """树形 DP：相邻两人不能同时选，返回整棵树的最大欢乐度。"""
    # 迭代代替递归：先取"父先于子"的遍历序，再倒序处理，孩子必然先于父亲算完
    order = [root]
    for boss in order:  # 遍历中列表不断变长，恰好把整棵树层展成一列
        order += children[boss]

    dp0 = [0] * len(joy)  # dp0[u]：u 不参加时，u 子树的最优欢乐度
    dp1 = joy[:]          # dp1[u]：u 参加时先记下 u 自己的欢乐度
    for boss in reversed(order):
        for emp in children[boss]:
            dp0[boss] += max(dp0[emp], dp1[emp])  # 上司不来，下属随意
            dp1[boss] += dp0[emp]                 # 上司来了，直接下属都不能来
    return max(dp0[root], dp1[root])  # 根来或不来取大；都不来即空名单，值为 0


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    joy = [0] + [next(data) for _ in range(n)]  # 下标 1..n 对齐员工编号

    # 关系行 "L K"：第 K 人是第 L 人的直接上司；0 0 结束
    children: dict[int, list[int]] = defaultdict(list)
    subordinate = set()
    while True:
        emp, boss = next(data), next(data)
        if emp == 0 and boss == 0:
            break
        children[boss].append(emp)
        subordinate.add(emp)
    # 树根 = 从没当过下属的人
    root = next(u for u in range(1, n + 1) if u not in subordinate)

    print(tree_dp(children, joy, root))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 00:48
 * update_at: 2026-10-06 00:48
 */
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

const ll MAXN = 6005; // 职员数上界 6000，多开一点

ll n; // 职员总数
ll joy[MAXN]; // joy[i]：第 i 个职员的欢乐度
vector<ll> children[MAXN]; // children[u]：u 的直接下属
bool has_boss[MAXN]; // has_boss[u]：u 是否有直接上司，用来找树根

ll dp0[MAXN]; // dp0[u]：u 不参加时，u 子树的最大欢乐度
ll dp1[MAXN]; // dp1[u]：u 参加时，u 子树的最大欢乐度
ll order[MAXN]; // order[]：父先于子的遍历序

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

    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> joy[i];
    }

    // 关系行 "L K"：K 是 L 的直接上司，输入以 0 0 结束
    ll emp = 0;
    ll boss = 0;
    while (cin >> emp >> boss) {
        if (emp == 0 && boss == 0) {
            break;
        }
        children[boss].push_back(emp);
        has_boss[emp] = true;
    }

    // 树根就是从没当过下属的人
    ll root = 1;
    for (ll u = 1; u <= n; u++) {
        if (!has_boss[u]) {
            root = u;
            break;
        }
    }

    // 先做一遍父先于子的遍历，得到 order[]
    ll head = 0;
    ll tail = 0;
    order[tail++] = root;
    while (head < tail) {
        ll u = order[head++];
        ll cnt = children[u].size();
        for (ll i = 0; i < cnt; i++) {
            order[tail++] = children[u][i];
        }
    }

    // 倒序遍历即后序：孩子必然先于父亲算完
    for (ll i = n - 1; i >= 0; i--) {
        ll u = order[i];
        dp1[u] = joy[u];
        ll cnt = children[u].size();
        for (ll j = 0; j < cnt; j++) {
            ll v = children[u][j];
            dp0[u] += max(dp0[v], dp1[v]); // u 不来，下属随意
            dp1[u] += dp0[v]; // u 来了，直接下属都不能来
        }
    }

    // 根来或不来取大；都不选即空名单，值为 0
    cout << max(dp0[root], dp1[root]) << '\n';
    return 0;
}