OneCoder Avatar
OneCodercoderli.com · 1025 篇博文
七级

C++ 算法考级专栏

🎨 视觉封面

【NOIP真题】2008 没有上司的舞会 luogu-P1352 | 适用于 GESP七级 / CSP-S 练习

📅 2026-10-06·✍️ OneCoder·计算中...·⏱️ 15 分钟

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

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

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

题目描述

某大学有 个职员,编号为 。

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

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

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

输入格式

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

第 到第 行,每行一个整数,第 行的整数表示 号职员的快乐指数 。

第 到第 行,每行输入一对整数 ,代表 是 的直接上司。

输出格式

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

样例 #1

样例输入 #1

Code14 行
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

样例输出 #1

Code1 行
5

提示

数据规模与约定

对于 的数据,保证 ,,,且给出的关系一定是一棵树。


题目深度剖析

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

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

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

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

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

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

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

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

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

状态机在树上的推导建立在父子关系的排他约束之上。设节点 的所有直接下属集合为 ,当其子节点 已经求得了最优解时:

  1. 若当前节点 参加舞会(计算 ):

    • 基础收益:职员 自身贡献快乐值 。
    • 排他约束:根据题目规定,若直接上司参会,下属无论如何不肯赴宴。因此,所有直接子节点 绝对不能参会,其状态被强制锁定为 。
    • 转移方程为:
  2. 若当前节点 不参加舞会(计算 ):

    • 基础收益:职员 未参会,基础收益为 。
    • 决策自由:直接上司不参会,下属 失去了来自上司的约束,既可以选择参会(获得子树收益 ),也可以选择不参会(获得子树收益 )。
    • 最优子结构:为了使全局快乐指数最大化,对每一个独立的子节点 ,我们都可以根据其收益权衡,自由选取两者的较大值:

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

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

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

  • 时间复杂度:
    • 寻找根节点只需线性扫描 ,耗时 ;
    • dfs 深度优先遍历过程中,每个节点被访问且仅被访问一次,总共 条有向树边被遍历一次;
    • 每个子节点向父节点的状态转移只包含加法和 max 比较,耗时 ;
    • 总时间复杂度严格为 。在 时,总操作量仅约 次,在评测机上耗时不足 ,远低于 的时限。
  • 空间复杂度:
    • 邻接表存储 条有向边,占用空间约 ;
    • 状态矩阵 占用内存 ;
    • 递归调用栈在树退化为单链的最坏情况下深度为 ,系统栈占用约数百 KB,远低于常规 的空间上限。总空间复杂度严格为 。

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

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

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

C++93 行
/**
 * 题目: 【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;
}
看完题解去实战!OneCoder C++ 信奥远征闯关平台 (oi.coderli.com)
💡 OneCoder 资源指引

所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI

🤝 技术交流与答疑

欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。

📚

猜你想读 · 相关文章推荐

OneCoder

OneCoder

一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

读者讨论与留言

共 0 条讨论
邮箱必填 · 支持 Markdown 格式与直接回复
💬 还没有读者留言,快来成为第一个讨论者吧!