P1352 没有上司的舞会

P1352 没有上司的舞会

在层级森严的树形组织架构中,上级与下属之间往往存在着天然的排他约束。洛谷 P1352「[NOIP2008 提高组] 没有上司的舞会」作为全国青少年信息学奥林匹克联赛(NOIP)与计算机学会认证(CCF GESP 七级、CSP-S 组)中最具标志性的经典树形动态规划(Tree DP)入门母题,其本质是图论中著名的**树的最大权独立集(Maximum Weight Independent Set on Trees)**问题。题目构建了一所大学内部以校长为根的层级从属树,核心矛盾在于:邀请任意职员赴宴均能获得快乐指数,但“直接上司赴宴则下属坚决不赴宴”的强排他规则打破了自顶向下的局部贪心可能。面对多叉树复杂的拓扑分支与可能存在的负权快乐值,贪心选择因后效性而失效。破局的关键在于抓住树结构的天然递归子结构——自底向上的树形状态机模型:针对每个节点抽象出「参加」与「不参加」两种互斥状态,利用后序遍历(DFS 深搜回溯)在子树全部决策完成后,由子节点向父节点无后效性地汇聚状态。该算法以优雅的 O(n)O(n) 线性时间与空间复杂度统揽全局最优解,题目洛谷官方难度评级为普及/提高-。

luogu-P1352 [NOIP2008 提高组] 没有上司的舞会

🔗 洛谷原题传送门:luogu-P1352 [NOIP2008 提高组] 没有上司的舞会

题目描述

某大学有 nn 个职员,编号为 1…n1\ldots n。

他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。

现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 rir_i,但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。

所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。

输入格式

输入的第一行是一个整数 nn。

第 22 到第 (n+1)(n + 1) 行,每行一个整数,第 (i+1)(i+1) 行的整数表示 ii 号职员的快乐指数 rir_i。

第 (n+2)(n + 2) 到第 2n2n 行,每行输入一对整数 l,kl, k,代表 kk 是 ll 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

样例 #1

样例输入 #1

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

样例输出 #1

5

提示

数据规模与约定

对于 100%100\% 的数据,保证 1≤n≤6×1031\leq n \leq 6 \times 10^3,−128≤ri≤127-128 \leq r_i\leq 127,1≤l,k≤n1 \leq l, k \leq n,且给出的关系一定是一棵树。


题目深度剖析

1. 贪心策略为何失效?(树的最大权独立集问题)

许多初学者面对此题容易直觉地联想到贪心策略:

  • 直觉贪心 1(按快乐值降序贪心):每次优先选择快乐指数 rir_i 最大的职员参会,然后将其直接上司和所有直接下属标记为不可参会。
    • 反例演示:设上司权值为 100100,其下有 1010 个直接下属,每个下属的权值均为 2020。贪心会直接挑选上司获得 100100 分,但若放弃上司,转而邀请全部 1010 名下属,总收益为 10×20=20010 \times 20 = 200 分,远高于贪心选择的 100100 分。
  • 直觉贪心 2(按奇偶树层染色贪心):将树按照深度进行二分图黑白二染色(类似选所有奇数层或所有偶数层)。
    • 反例演示:树的结构是不规则的。可能某个分支在深度为 1 的点权值极高,而另一个深分支在深度为 2 的点权值极高。全局按深度分层会割裂各子树内部的最优选择。

本质归纳:本题等价于图论中的带权最大独立集(Maximum Weight Independent Set)。在一般无向图上,最大独立集属于著名的 NP-Hard 难题;然而,当图的拓扑结构退化为**无环连通图——树(Tree)时,树的天然拓扑分层与子树互不干扰的独立性,使得问题可以通过动态规划(DP)**在严格的线性时间 O(n)O(n) 内求出全局精确最优解。

2. 状态设计与树形状态机模型

在树结构上进行动态规划,核心在于:以节点在树中的从属层次作为阶段,自底向上(从叶子到根)递推求解。

每个职员(节点 uu)在舞会中仅有两种互斥状态:参加 或 不参加。因此,我们针对每个节点定义两个维度的状态变量:

  • dp[u][0]dp[u][0]:表示职员 uu 不参加舞会时,以 uu 为根节点的整棵子树所能获得的最大快乐指数;
  • dp[u][1]dp[u][1]:表示职员 uu 参加舞会时,以 uu 为根节点的整棵子树所能获得的最大快乐指数。

3. 状态转移方程与推导逻辑

状态机在树上的推导建立在父子关系的排他约束之上。设节点 uu 的所有直接下属集合为 children(u)\text{children}(u),当其子节点 v∈children(u)v \in \text{children}(u) 已经求得了最优解时:

  1. 若当前节点 uu 参加舞会(计算 dp[u][1]dp[u][1]):

    • 基础收益:职员 uu 自身贡献快乐值 rur_u。
    • 排他约束:根据题目规定,若直接上司参会,下属无论如何不肯赴宴。因此,所有直接子节点 vv 绝对不能参会,其状态被强制锁定为 dp[v][0]dp[v][0]。
    • 转移方程为: dp[u][1]=ru+∑v∈children(u)dp[v][0]dp[u][1] = r_u + \sum_{v \in \text{children}(u)} dp[v][0]
  2. 若当前节点 uu 不参加舞会(计算 dp[u][0]dp[u][0]):

    • 基础收益:职员 uu 未参会,基础收益为 00。
    • 决策自由:直接上司不参会,下属 vv 失去了来自上司的约束,既可以选择参会(获得子树收益 dp[v][1]dp[v][1]),也可以选择不参会(获得子树收益 dp[v][0]dp[v][0])。
    • 最优子结构:为了使全局快乐指数最大化,对每一个独立的子节点 vv,我们都可以根据其收益权衡,自由选取两者的较大值: dp[u][0]=∑v∈children(u)max⁡(dp[v][0],dp[v][1])dp[u][0] = \sum_{v \in \text{children}(u)} \max(dp[v][0], dp[v][1])

4. 树结构的存储与树根(校长)的确定

  1. 存储结构选择:
    • 本题 n≤6000n \le 6000,属于稀疏树图。输入给出从属关系为“kk 是 ll 的直接上司”,即存在一条由父节点指向子节点的有向边 k→lk \to l。
    • 采用 std::vector<int> tree_edges[MAXN] 邻接表存储树的拓扑关系,能够兼顾清晰的语义与高效的常数遍历性能。
  2. 寻找整棵树的根节点(校长):
    • 题目并未直接指明谁是校长(树根)。但树具有核心性质:除根节点外,每个节点都有且仅有一个唯一的父节点;而根节点的父节点不存在(入度为 0)。
    • 我们维护布尔数组 has_parent[l] = true 记录所有被作为下属出现的节点。读入所有边后,在 1∼n1 \sim n 中遍历寻找唯一的 has_parent[root] == false 的节点,即为整棵树的根节点。
  3. 遍历顺序与无后效性保证:
    • 树形 DP 必须保证:在计算父节点 uu 的 DP 值之前,其所有子节点 vv 的 DP 值已经完全计算完毕。
    • 因此,从根节点调用深度优先搜索 dfs(root),在后序遍历回溯阶段完成状态转移,天然满足拓扑计算次序,绝对保证状态的无后效性。

5. 复杂度剖析与运行指标

  • 时间复杂度:
    • 寻找根节点只需线性扫描 1∼n1 \sim n,耗时 O(n)O(n);
    • dfs 深度优先遍历过程中,每个节点被访问且仅被访问一次,总共 n−1n - 1 条有向树边被遍历一次;
    • 每个子节点向父节点的状态转移只包含加法和 max 比较,耗时 O(1)O(1);
    • 总时间复杂度严格为 O(n)O(n)。在 n=6000n = 6000 时,总操作量仅约 1.2×1041.2 \times 10^4 次,在评测机上耗时不足 1 ms1 \text{ ms},远低于 1.0 s1.0 \text{ s} 的时限。
  • 空间复杂度:
    • 邻接表存储 n−1n - 1 条有向边,占用空间约 6000×4 B≈24 KB6000 \times 4 \text{ B} \approx 24 \text{ KB};
    • 状态矩阵 dp[6005][2]dp[6005][2] 占用内存 6005×2×4 B≈48 KB6005 \times 2 \times 4 \text{ B} \approx 48 \text{ KB};
    • 递归调用栈在树退化为单链的最坏情况下深度为 n=6000n = 6000,系统栈占用约数百 KB,远低于常规 128 MB128 \text{ MB} 的空间上限。总空间复杂度严格为 O(n)O(n)。

6. 核心考点与竞赛避坑指南

  1. 负权快乐值的自然规避:
    • 题目数据范围中快乐值 −128≤ri≤127-128 \le r_i \le 127,存在大量负权。
    • 初学者常困惑:若叶子节点全为负数,是否必须选人?
    • 观察转移方程:若下属 vv 为负权叶子节点,则 dp[v][1]=rv<0dp[v][1] = r_v < 0,而 dp[v][0]=0dp[v][0] = 0。当父节点不选时,max⁡(dp[v][0],dp[v][1])=max⁡(0,rv)=0\max(dp[v][0], dp[v][1]) = \max(0, r_v) = 0,算法会自动放弃邀请负收益职员。
  2. 单节点边界特判(n=1n = 1):
    • 当学校仅有校长 11 人时,n=1n = 1,边数为 00。循环读入边不执行,has_parent[1] 保持 false,判定根为 11。dfs(1) 直接赋初值 dp[1][0]=0,dp[1][1]=r1dp[1][0] = 0, dp[1][1] = r_1。最终输出 max⁡(0,r1)\max(0, r_1),完全契合题意。
  3. 全局答案的最终统计:
    • 最终的答案即为整棵树在根节点 root 决策下的最大值,即 max⁡(dp[root][0],dp[root][1])\max(dp[root][0], dp[root][1]),切勿遗漏根节点不参会的可能性。

完整参考代码(C++11 规范)

/**
 * 题目: 【GESP/CSP练习】GESP七级 / CSP-S 题解:luogu-P1352 [NOIP2008 提高组] 没有上司的舞会
 * 题号: P1352
 * 归属: GESP七级 / CSP-S / 树形动态规划经典题
 * 博客: https://www.coderli.com/gesp-7-luogu-p1352/
 * 标准: C++11 (严格遵循 CCF GESP 官方规范)
 */

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// 最大职员数常量定义,题目中 n <= 6000
const int MAXN = 6005;

// r 数组存储每位职员的快乐指数
int r[MAXN];

// 邻接表存储树形从属关系:tree_edges[k] 存储直接上司 k 的所有直接下属 l
vector<int> tree_edges[MAXN];

// has_parent 标记职员是否有直接上司,用于寻找整棵树的根节点(校长)
bool has_parent[MAXN];

// dp[u][0]: 职员 u 不参加舞会时,以 u 为根的子树所能获得的最大快乐指数
// dp[u][1]: 职员 u 参加舞会时,以 u 为根的子树所能获得的最大快乐指数
int dp[MAXN][2];

/**
 * 深度优先搜索(DFS)后序遍历实现树形动态规划
 * 自底向上:先递归处理所有子节点,再根据子节点的最优状态计算父节点的最优状态
 * @param u 当前访问的节点编号
 */
void dfs(int u) {
    // 基础状态初始化:
    // 若 u 不参加,初始快乐指数为 0
    dp[u][0] = 0;
    // 若 u 参加,初始快乐指数为职员自身的快乐值 r[u]
    dp[u][1] = r[u];

    // 遍历当前节点 u 的所有直接下属 v
    for (int v : tree_edges[u]) {
        // 递归求解子树 v 的最优解
        dfs(v);

        // 状态转移 1:如果直接上司 u 不参加舞会,
        // 则直接下属 v 既可以参加也可以不参加,二者取较大值进行累加
        dp[u][0] += max(dp[v][0], dp[v][1]);

        // 状态转移 2:如果直接上司 u 参加舞会,
        // 则直接下属 v 无论如何都不能参加,只能选择 dp[v][0] 进行累加
        dp[u][1] += dp[v][0];
    }
}

int main() {
    int n;
    cin >> n;

    // 读入每位职员的快乐指数(1 号至 n 号)
    for (int i = 1; i <= n; ++i) {
        cin >> r[i];
    }

    // 读入 n - 1 条从属从属关系边
    // 题目给出每行 l, k,表示 k 是 l 的直接上司,即 k 为父节点,l 为子节点
    for (int i = 1; i < n; ++i) {
        int l, k;
        cin >> l >> k;
        tree_edges[k].push_back(l);
        has_parent[l] = true;
    }

    // 寻找整棵从属树的根节点(校长)
    // 根节点没有直接上司,因此 has_parent[root] 为 false
    int root = 1;
    for (int i = 1; i <= n; ++i) {
        if (!has_parent[i]) {
            root = i;
            break;
        }
    }

    // 从根节点出发执行树形 DP
    dfs(root);

    // 全局最优解为校长参加与不参加两种情况下的较大值
    cout << max(dp[root][0], dp[root][1]) << endl;

    return 0;
}

本文由coderli.com原创,按照CC BY-NC-SA 4.0 进行授权

所有代码已上传至Github:https://github.com/lihongzheshuai/yummy-code

“luogu-”系列题目可在 洛谷题库 在线评测。

“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群: 688906745

GESP/CSP 认证学习微信公众号
GESP/CSP 认证学习微信公众号
最后更新于