C++ 算法考级专栏
🎨 视觉封面【NOIP真题】2008 没有上司的舞会 luogu-P1352 | 适用于 GESP七级 / CSP-S 练习
在层级森严的树形组织架构中,上级与下属之间往往存在着天然的排他约束。洛谷 P1352「[NOIP2008 提高组] 没有上司的舞会」作为全国青少年信息学奥林匹克联赛(NOIP)与计算机学会认证(CCF GESP 七级、CSP-S 组)中最具标志性的经典树形动态规划(Tree DP)入门母题,其本质是图论中著名的**树的最大权独立集(Maximum Weight Independent Set on Trees)**问题。题目构建了一所大学内部以校长为根的层级从属树,核心矛盾在于:邀请任意职员赴宴均能获得快乐指数,但“直接上司赴宴则下属坚决不赴宴”的强排他规则打破了自顶向下的局部贪心可能。面对多叉树复杂的拓扑分支与可能存在的负权快乐值,贪心选择因后效性而失效。破局的关键在于抓住树结构的天然递归子结构——自底向上的树形状态机模型:针对每个节点抽象出「参加」与「不参加」两种互斥状态,利用后序遍历(DFS 深搜回溯)在子树全部决策完成后,由子节点向父节点无后效性地汇聚状态。该算法以优雅的 线性时间与空间复杂度统揽全局最优解,题目洛谷官方难度评级为普及/提高-。
luogu-P1352 [NOIP2008 提高组] 没有上司的舞会
🔗 洛谷原题传送门:luogu-P1352 [NOIP2008 提高组] 没有上司的舞会
题目描述
某大学有 个职员,编号为 。
他们之间有从属关系,也就是说他们的关系就像一棵以校长为根的树,父结点就是子结点的直接上司。
现在有个周年庆宴会,宴会每邀请来一个职员都会增加一定的快乐指数 ,但是呢,如果某个职员的直接上司来参加舞会了,那么这个职员就无论如何也不肯来参加舞会了。
所以,请你编程计算,邀请哪些职员可以使快乐指数最大,求最大的快乐指数。
输入格式
输入的第一行是一个整数 。
第 到第 行,每行一个整数,第 行的整数表示 号职员的快乐指数 。
第 到第 行,每行输入一对整数 ,代表 是 的直接上司。
输出格式
输出一行一个整数代表最大的快乐指数。
样例 #1
样例输入 #1
7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5样例输出 #1
5提示
数据规模与约定
对于 的数据,保证 ,,,且给出的关系一定是一棵树。
题目深度剖析
1. 贪心策略为何失效?(树的最大权独立集问题)
许多初学者面对此题容易直觉地联想到贪心策略:
- 直觉贪心 1(按快乐值降序贪心):每次优先选择快乐指数 最大的职员参会,然后将其直接上司和所有直接下属标记为不可参会。
- 反例演示:设上司权值为 ,其下有 个直接下属,每个下属的权值均为 。贪心会直接挑选上司获得 分,但若放弃上司,转而邀请全部 名下属,总收益为 分,远高于贪心选择的 分。
- 直觉贪心 2(按奇偶树层染色贪心):将树按照深度进行二分图黑白二染色(类似选所有奇数层或所有偶数层)。
- 反例演示:树的结构是不规则的。可能某个分支在深度为 1 的点权值极高,而另一个深分支在深度为 2 的点权值极高。全局按深度分层会割裂各子树内部的最优选择。
本质归纳:本题等价于图论中的带权最大独立集(Maximum Weight Independent Set)。在一般无向图上,最大独立集属于著名的 NP-Hard 难题;然而,当图的拓扑结构退化为**无环连通图——树(Tree)时,树的天然拓扑分层与子树互不干扰的独立性,使得问题可以通过动态规划(DP)**在严格的线性时间 内求出全局精确最优解。
2. 状态设计与树形状态机模型
在树结构上进行动态规划,核心在于:以节点在树中的从属层次作为阶段,自底向上(从叶子到根)递推求解。
每个职员(节点 )在舞会中仅有两种互斥状态:参加 或 不参加。因此,我们针对每个节点定义两个维度的状态变量:
- :表示职员 不参加舞会时,以 为根节点的整棵子树所能获得的最大快乐指数;
- :表示职员 参加舞会时,以 为根节点的整棵子树所能获得的最大快乐指数。
3. 状态转移方程与推导逻辑
状态机在树上的推导建立在父子关系的排他约束之上。设节点 的所有直接下属集合为 ,当其子节点 已经求得了最优解时:
-
若当前节点 参加舞会(计算 ):
- 基础收益:职员 自身贡献快乐值 。
- 排他约束:根据题目规定,若直接上司参会,下属无论如何不肯赴宴。因此,所有直接子节点 绝对不能参会,其状态被强制锁定为 。
- 转移方程为:
-
若当前节点 不参加舞会(计算 ):
- 基础收益:职员 未参会,基础收益为 。
- 决策自由:直接上司不参会,下属 失去了来自上司的约束,既可以选择参会(获得子树收益 ),也可以选择不参会(获得子树收益 )。
- 最优子结构:为了使全局快乐指数最大化,对每一个独立的子节点 ,我们都可以根据其收益权衡,自由选取两者的较大值:
4. 树结构的存储与树根(校长)的确定
- 存储结构选择:
- 本题 ,属于稀疏树图。输入给出从属关系为“ 是 的直接上司”,即存在一条由父节点指向子节点的有向边 。
- 采用
std::vector<int> tree_edges[MAXN]邻接表存储树的拓扑关系,能够兼顾清晰的语义与高效的常数遍历性能。
- 寻找整棵树的根节点(校长):
- 题目并未直接指明谁是校长(树根)。但树具有核心性质:除根节点外,每个节点都有且仅有一个唯一的父节点;而根节点的父节点不存在(入度为 0)。
- 我们维护布尔数组
has_parent[l] = true记录所有被作为下属出现的节点。读入所有边后,在 中遍历寻找唯一的has_parent[root] == false的节点,即为整棵树的根节点。
- 遍历顺序与无后效性保证:
- 树形 DP 必须保证:在计算父节点 的 DP 值之前,其所有子节点 的 DP 值已经完全计算完毕。
- 因此,从根节点调用深度优先搜索
dfs(root),在后序遍历回溯阶段完成状态转移,天然满足拓扑计算次序,绝对保证状态的无后效性。
5. 复杂度剖析与运行指标
- 时间复杂度:
- 寻找根节点只需线性扫描 ,耗时 ;
dfs深度优先遍历过程中,每个节点被访问且仅被访问一次,总共 条有向树边被遍历一次;- 每个子节点向父节点的状态转移只包含加法和
max比较,耗时 ; - 总时间复杂度严格为 。在 时,总操作量仅约 次,在评测机上耗时不足 ,远低于 的时限。
- 空间复杂度:
- 邻接表存储 条有向边,占用空间约 ;
- 状态矩阵 占用内存 ;
- 递归调用栈在树退化为单链的最坏情况下深度为 ,系统栈占用约数百 KB,远低于常规 的空间上限。总空间复杂度严格为 。
6. 核心考点与竞赛避坑指南
- 负权快乐值的自然规避:
- 题目数据范围中快乐值 ,存在大量负权。
- 初学者常困惑:若叶子节点全为负数,是否必须选人?
- 观察转移方程:若下属 为负权叶子节点,则 ,而 。当父节点不选时,,算法会自动放弃邀请负收益职员。
- 单节点边界特判():
- 当学校仅有校长 人时,,边数为 。循环读入边不执行,
has_parent[1]保持false,判定根为 。dfs(1)直接赋初值 。最终输出 ,完全契合题意。
- 当学校仅有校长 人时,,边数为 。循环读入边不执行,
- 全局答案的最终统计:
- 最终的答案即为整棵树在根节点
root决策下的最大值,即 ,切勿遗漏根节点不参会的可能性。
- 最终的答案即为整棵树在根节点
完整参考代码(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;
}所有代码开源上传至 GitHub:yummy-code 仓库 · GESP 专题站:GESP WIKI
欢迎加入:C++ GESP/CSP 考级答疑群(688906745) 与 Java/Python交流群(982860385),点击可直接加群。
猜你想读 · 相关文章推荐
【GESP真题】GESP七级 / CSP-S 题解:luogu-P17460 [GESP202609 七级] 括号序列
CCF GESP 2026年9月认证(第十五次认证)C++ 七级试题,洛谷 P17460。本题严格遵循 CCF GESP 官方大纲规范,重点考察括号序列平衡度与子序列计数DP。题目逻辑严密,模型典型,是深入理解与掌握信奥核心考点的经典范例。
【GESP】C++七级考试大纲知识点梳理, (2) 复杂动态规划
GESP C++七级考试大纲的第2条考点是整个七级的“重头戏”——复杂动态规划。相比于低级别的线性DP,七级要求掌握更复杂的模型(如区间DP)以及处理两个序列的问题(LCS),同时对空间复杂度优化提出了明确要求。 (2)掌握复杂动态规划(二维动态规划、动态规划最值优化)...
【GESP真题】GESP七级 / CSP-S 题解:luogu-P17459 [GESP202609 七级] 必经之路
CCF GESP 2026年9月认证(第十五次认证)C++ 七级试题,洛谷 P17459。本题严格遵循 CCF GESP 官方大纲规范,重点考察图论·全源可达性与割点检测。题目逻辑严密,模型典型,是深入理解与掌握信奥核心考点的经典范例。
OneCoder
一个中年人的自留地,记录学习 C++、GESP/NOI、Java、Python 与算法架构的心得体会。本站唯一网址:coderli.com

