形式化题目

给定一棵 $N$ 个节点的有根树 $T = (V, E)$，根为 $r$（校长），每个节点 $v$ 有权值 $H_v$。要求选出顶点子集 $S \subseteq V$，使得 $T$ 中任意一条边的两个端点不同时属于 $S$（没有职员愿意和直接上司一起参会），并最大化 $\sum_{v \in S} H_v$。

即：求树上带权最大独立集。注意权值可以是负数，因此 $S = \varnothing$ 也是合法方案。

输入中每条边以 L K 给出，含义是「$K$ 是 $L$ 的直接上司」，也就是树上的 $K$ 是 $L$ 的父亲，根由「没有任何上司」的那唯一一个节点确定。

样例的树形结构如下，括号内是快乐指数：

1
2
3
4
5                  5(1)              <- 校长（根），他没有上司
                /      \
            3(1)        4(1)
           /    \      /    \
        1(1)  2(1)  6(1)  7(1)

读边时要注意方向：1 3 表示 3 是 1 的上司（3 是父亲），3 5 表示 5 是 3 的上司。全部权值都是 $1$，所以答案等于最大独立集的大小。只取一棵子树的叶子（如 $\{1, 2\}$）或只取中间层（如 $\{3, 4\}$）最多得到 2 个点，再往上加就会撞上父子冲突；样例的最优解是 $\{5, 1, 2, 6, 7\}$——让校长 5 参会，则他的两个下属 3、4 都不能来，但四个叶子可以全部参会，共 5 个点，输出 5。

正解

思路

先看为什么不能直接枚举。 把「谁参会」写成 0/1 向量 $x_1, \dots, x_N$，约束是每条父子边两端不能同为 1，要求最大化 $\sum x_v H_v$。枚举全部 $2^N$ 个子集在 $N \leqslant 6000$ 时不可能，而题目给出的约束是逐边的：一个点选不选，只影响它的父亲和儿子，不影响更远的节点。既然约束是局部的，就应该把决策按树分解。

关键观察：父亲只需要两档信息。 固定一个节点 $v$ 之后，$v$ 的各个儿子的子树彼此独立：它们之间没有边相连，而且 $v$ 的子树与外界唯一的联系就是 $v$ 自己。所以「$v$ 子树内部的最优值」是一个可以独立计算、独立复用的量。再从 $v$ 的父亲的角度看，它唯一关心的是「$v$ 到底选没选」：

• 如果 $v$ 参会，父亲就不能参会；
• 如果 $v$ 不参会，父亲可以自由决定。

子树内部的细节（孙子们怎么选）对父亲完全没有影响。于是每个点只需要保存两档答案：

• $f[v][1]$：$v$ 参会时，$v$ 子树内的最大快乐值；
• $f[v][0]$：$v$ 不参会时，$v$ 子树内的最大快乐值。

转移。 设 $u$ 取遍 $v$ 的所有儿子：

第一式的道理是：$v$ 参会则每个儿子都不能参会，儿子那部分只能取 $f[u][0]$；第二式是：$v$ 不参会则每个儿子各自挑更好的那一档，父子独立性让「每棵子树各取最优」可以直接相加。叶子没有儿子，两个式子退化为基础情形 $f[\text{leaf}][1] = H_{\text{leaf}}$、$f[\text{leaf}][0] = 0$；负权点也因此会被自然跳过，因为不参会那一档的 $\max$ 不强迫取负数。

计算顺序。 $f[v][\cdot]$ 依赖儿子，儿子的答案又依赖孙子，所以必须「儿子先于父亲」计算，也就是后序遍历。本题 $N$ 可达 $6000$，一条链会让递归深度爆掉；代码不用 sys.setrecursionlimit，而是用显式栈先做一次前序（先压父亲、再压儿子），再把顺序反过来，就得到后序。

样例的树共有 7 个节点、6 条边，深度为 3。代码得到的后序处理顺序是 $6, 7, 4, 1, 2, 3, 5$（兄弟之间的先后只取决于孩子表里的顺序，任意一种后序都正确）。按这个顺序推演，每行给出该节点两档状态的初值（$f[v][1]$ 初值为 $H_v$，$f[v][0]$ 初值为 $0$）以及加上全部儿子贡献后的最终值：

观察这张表：叶子那几行的两档是 $(0, H_v)$，都只由它自己的权值决定；中间节点 3、4 的「不参会」档（$2$）反而比「参会」档（$1$）大，因为放弃自己可以换来两个儿子各贡献 $1$；根节点 5 的「参会」档是 $H_5$ 加上两个儿子被锁死的 $f[u][0]$，即 $1+2+2=5$，而「不参会」档是两个儿子各自的较大者之和 $\max(1,2)+\max(1,2)=4$，答案是 $\max(4,5)=5$，与样例输出一致。

正确性。 对子树节点数归纳：叶子情形显然成立。设 $v$ 的每个儿子的两档值都已按定义算好。若 $v$ 参会，则任一儿子 $u$ 都不能参会，$u$ 的子树只能取 $f[u][0]$，且各儿子子树之间没有边相连、贡献可加，故最优值为 $H_v + \sum_u f[u][0]$；若 $v$ 不参会，则每个儿子 $u$ 在参不参会之间自由，取 $\max(f[u][0], f[u][1])$，各子树独立故求和即最优。$v$ 子树与外界的唯一联系是 $v$ 本身，因此这两档值携带了上层需要的全部信息，父节点据此决策不会漏掉任何方案。根没有上司，两档都可取，答案是 $\max(f[\text{root}][0], f[\text{root}][1])$。后序遍历保证处理 $v$ 时儿子都已经算好，归纳成立。

代码

read_tree 一边建孩子表一边标记「有上司」，没被标记过的那个点就是校长；postorder 用显式栈得到后序；attend 与 absent 分别就是 $f[\cdot][1]$ 与 $f[\cdot][0]$，其中 attend = happy[:] 顺手把 $+H_v$ 这一项初始化好了。

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/**
 * 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-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 没有上司的舞会：树上最大权独立集，按后序递推每个点的两档状态。
#include <cstdio>
#include <vector>

typedef long long ll;

ll n;
std::vector<ll> happy;
std::vector<std::vector<int> > children;
std::vector<char> has_boss;
std::vector<ll> attend, absent;

int main() {
    if (scanf("%lld", &n) != 1) return 0;
    happy.assign(n + 1, 0);
    for (ll i = 1; i <= n; i++) scanf("%lld", &happy[i]);

    children.assign(n + 1, std::vector<int>());
    has_boss.assign(n + 1, 0);
    for (ll i = 0; i < n - 1; i++) {
        int child, boss;
        if (scanf("%d %d", &child, &boss) != 2) break;
        children[boss].push_back(child);
        has_boss[child] = 1;
    }
    ll root = 1;
    for (ll i = 1; i <= n; i++) {
        if (!has_boss[i]) {
            root = i;
            break;
        }
    }

    // 后序遍历整棵树：显式栈先压出「父在子前」，反转就是「子在父前」
    std::vector<int> order;
    std::vector<int> stk;
    stk.push_back((int)root);
    while (!stk.empty()) {
        int u = stk.back();
        stk.pop_back();
        order.push_back(u);
        for (size_t j = 0; j < children[u].size(); j++) stk.push_back(children[u][j]);
    }

    attend.assign(n + 1, 0);
    absent.assign(n + 1, 0);
    for (ll i = 1; i <= n; i++) attend[i] = happy[i];
    for (size_t t = order.size(); t-- > 0;) {
        int u = order[t];
        for (size_t j = 0; j < children[u].size(); j++) {
            int v = children[u][j];
            attend[u] += absent[v];                              // f[u][1] += f[儿子][0]
            absent[u] += (attend[v] > absent[v] ? attend[v] : absent[v]); // f[u][0] += max(...)
        }
    }
    printf("%lld\n", attend[root] > absent[root] ? attend[root] : absent[root]);
    return 0;
}

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#!/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-10-01 20:56
# update_at: 2026-10-01 21:00

import sys
from collections.abc import Iterator


def read_tree(data: Iterator[int], n: int) -> tuple[list[list[int]], int]:
    """读 N-1 行「K 是 L 的直接上司」，返回孩子表和校长编号。"""
    children: list[list[int]] = [[] for _ in range(n + 1)]
    has_boss = bytearray(n + 1)  # 有上司的职员置 1，没被置位的唯一一个就是校长
    for _ in range(n - 1):
        child, boss = next(data), next(data)
        children[boss].append(child)
        has_boss[child] = 1
    return children, next(i for i in range(1, n + 1) if not has_boss[i])


def postorder(children: list[list[int]], root: int) -> Iterator[int]:
    """后序遍历整棵树：最坏是一条 3000 层的链，显式栈比递归稳。"""
    order: list[int] = []
    stack = [root]
    while stack:
        node = stack.pop()
        order.append(node)      # 先父后子地压出顺序
        stack += children[node]
    yield from reversed(order)  # 反过来就是「儿子先于父亲」的后序


def best_happiness(children: list[list[int]], happy: list[int], root: int) -> int:
    """树上最大权独立集：按后序递推每个点的两档状态，返回根节点两档中的较大者。"""
    attend = happy[:]             # attend[v]：v 参会时 v 子树的答案，此时儿子一律不能参会
    absent = [0] * len(happy)     # absent[v]：v 不参会时 v 子树的答案，儿子各自自由取舍
    for node in postorder(children, root):
        for child in children[node]:
            attend[node] += absent[child]                          # f[v][1] += f[儿子][0]
            absent[node] += max(attend[child], absent[child])      # f[v][0] += max(f[儿子][0], f[儿子][1])
    return max(attend[root], absent[root])


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    happy = [0] + [next(data) for _ in range(n)]  # happy[0] 是让下标从 1 开始的占位
    children, root = read_tree(data, n)

    print(best_happiness(children, happy, root))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O(N)$。建树、找根、生成后序各扫一遍 $N$ 个节点；转移时每个节点只被处理一次，处理时遍历它的儿子，而所有节点的儿子总数恰好是 $N-1$，故转移总量也是 $O(N)$。
• 空间复杂度：$O(N)$。孩子表存 $N-1$ 条边，happy／attend／absent／has_boss 各 $O(N)$，显式栈和后序序列各 $O(N)$。

总结

本题是树形 DP 的入门模型，核心是把「选哪些人」这个大决策换成「每个点选或不选」的两档局部状态：约束只在父子之间，所以父亲只需要知道儿子选没选，子树内部的细节可以提前压缩成一个数。固定这点之后，转移式就是从「父亲与儿子不能同时被选」直接翻译过来的两条加和；唯一需要额外注意的是计算顺序——依赖指向儿子，就必须后序遍历，而 $N$ 较大时用显式栈代替递归更稳妥。

图示解析

这张图串起本题从建模到得到答案的主线：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19输入：一棵以校长为根的树，每个职员有权值
  |
  |  枚举 2^N 个参会子集不可行（N 可达 6000）
  v
关键观察：约束只发生在相邻的父子之间
  |- 固定 v 后，各个儿子子树彼此独立
  `- 父亲关心的只有「v 选没选」两件事
        |
        v
  每个点两档状态：f[v][1] 参会 / f[v][0] 不参会
        |
        |  f[v][1] = H_v + Σ f[u][0]         （v 来，儿子都不能来）
        |  f[v][0] = Σ max(f[u][0], f[u][1]) （v 不来，儿子各自挑最优）
        v
  计算顺序：后序遍历，儿子先于父亲
        |
        |  显式栈代替递归，避免 6000 层链爆栈
        v
  答案 max(f[root][0], f[root][1])        O(N) 时间、O(N) 空间

观察重点：整条链路上真正的转折点只有一处——把「全局选一个子集」变成「每个点两档状态」。递推式本身只是「父子不能同时参会」的逐字翻译：$v$ 参会时儿子那一项被锁死为 $f[u][0]$，$v$ 不参会时儿子那一项放开为两者取大。最后的 max 之所以只在根节点做，是因为其余节点的取舍已经全部被父节点在递推时考虑过了。