没有上司的舞会

形式化题目

给定一棵包含 $n$ 个结点的有根树，每个结点 $i$ 有点权 $r_i$ 。

从树中选取一个结点子集，满足任意一条树边连接的两个结点不能被同时选中（即选出的点互不相邻，构成独立集）。求被选结点的权值之和的最大值。

暴力解法

思路

每个结点只有“选入集合”与“不选入集合”两种决策。

可以通过递归 DFS 枚举所有 $2^n$ 种选点方案。当所有点的选择状态确定后，遍历树上的每条从属边 $(k, l)$ 。若存在某条边的父结点和子结点同时被选中，则该方案非法；否则累加所有选中结点的权值之和，维护全局最大值。

代码

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据枚举每个员工是否参加，检查上下级冲突。

const int MAXN = 25;

int n;
int happy[MAXN];
int child_node[MAXN], parent_node[MAXN];
int choose_flag[MAXN];
int answer;

void dfs_enum(int pos) {
    if (pos == n + 1) {
        for (int i = 1; i < n; i++) {
            if (choose_flag[child_node[i]] && choose_flag[parent_node[i]]) {
                return;
            }
        }

        int sum = 0;
        for (int i = 1; i <= n; i++) {
            if (choose_flag[i]) {
                sum += happy[i];
            }
        }
        answer = max(answer, sum);
        return;
    }

    choose_flag[pos] = 0;
    dfs_enum(pos + 1);
    choose_flag[pos] = 1;
    dfs_enum(pos + 1);
}

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

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> happy[i];
    }
    for (int i = 1; i < n; i++) {
        cin >> child_node[i] >> parent_node[i];
    }

    answer = 0;
    dfs_enum(1);
    cout << answer << '\n';

    return 0;
}

复杂度

时间复杂度：枚举 $n$ 个结点的状态需要 $O(2^n)$ 次递归，对每种方案校验边并求和需要 $O(n)$ ，总时间复杂度为 $O(n \cdot 2^n)$ 。
空间复杂度：递归深度与状态标记数组占用 $O(n)$ 空间。

瓶颈

方案枚举是全局的盲目搜索。实际上，结点 $u$ 是否被选择，仅直接制约其孩子结点的选择，对子树之外的结构没有跨层约束。树上不同子树之间相对独立，存在大量重叠子问题，适合通过树形动态规划自底向上合并最优决策。

正解

思路

本题是树上最大权独立集的经典模型。

考虑树的无后向性：在以 $u$ 为根的子树中，是否选取 $u$ 完全决定了其所有直接孩子 $v$ 的状态约束：

若不选 $u$ ：每个直接孩子 $v$ 既可以选，也可以不选，各孩子子树之间相互独立，贪心选取各自的最优方案。
若选择 $u$ ：根据题意，其所有直接孩子 $v$ 都不能被选择，每个孩子子树只能取不选 $v$ 的最优方案。

状态设计

定义：

$dp[u][0]$ 表示不选结点 $u$ 时，以 $u$ 为根的子树所能获得的最大权值和。
$dp[u][1]$ 表示选择结点 $u$ 时，以 $u$ 为根的子树所能获得的最大权值和。

状态转移方程

自底向上遍历每个结点 $u$ 及其孩子集合 $children(u)$ ：

基础值初始化： $dp[u][0] = 0$ ， $dp[u][1] = r_u$ 。
遍历直接孩子 $v \in children(u)$ ：
$dp[u][0] = \sum_{v \in children(u)} \max(dp[v][0], dp[v][1])$

$dp[u][1] = r_u + \sum_{v \in children(u)} dp[v][0]$

求解流程

读入数据建有向树（由父结点连向子结点），通过入度数组标记有父结点的点，未被标记的即为整棵树的根结点 $root$ 。
从 $root$ 出发进行一次后序深度优先搜索（DFS），先递归求解所有孩子子树的 DP 值，再聚合得到当前结点的 DP 值。
最终答案即为根结点选或不选两种情况的最大值： $\max(dp[root][0], dp[root][1])$ 。

代码

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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 6005;

int n;
int happy[MAXN];
vector<int> children[MAXN];
bool has_parent[MAXN];
int dp[MAXN][2]; // dp[u][0]：不选 u 的最大快乐值；dp[u][1]：选择 u 的最大快乐值。

void read_input() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> happy[i];
    }

    for (int i = 1; i < n; i++) {
        int child, parent;
        cin >> child >> parent;
        children[parent].push_back(child);
        has_parent[child] = true;
    }
}

void dfs(int u) {
    dp[u][0] = 0;
    dp[u][1] = happy[u];

    for (int i = 0; i < (int)children[u].size(); i++) {
        int v = children[u][i];
        dfs(v);

        // 不选 u 时，孩子 v 可选可不选，取更优。
        dp[u][0] += max(dp[v][0], dp[v][1]);

        // 选择 u 时，直接下属 v 不能参加。
        dp[u][1] += dp[v][0];
    }
}

void solve() {
    int root = 1;
    for (int i = 1; i <= n; i++) {
        if (!has_parent[i]) {
            root = i;
            break;
        }
    }

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

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度：DFS 遍历整棵树，每个结点和每条边各访问一次，单次状态转移为 $O(1)$ ，总时间复杂度为 $O(n)$ 。在 $n \le 6000$ 规模下可毫秒级完成。
空间复杂度：邻接表存树需要 $O(n)$ 空间，DP 数组和递归调用栈各占 $O(n)$ 空间，总空间复杂度为 $O(n)$ 。

总结

树形 DP 的核心抓手在于分析“父结点与子结点的状态约束关系”。

在本题中，约束关系极其明确：选了父亲就绝对不能选孩子；不选父亲则孩子选不选均可。因此仅需用 $0/1$ 两个布尔维度刻画根结点的决策状态，子树间独立性保证了局部最优可以直接累加为全局最优。

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

状态设计

状态转移方程

求解流程

代码

复杂度

总结