选点 / 最大独立集
没有上司的舞会
本课摘要
选点 / 最大独立集课程回答“父子不能同时选择时，选与不选状态如何配合”。内容以没有上司的舞会为主线，配合逐步推导、可编辑演示、例题与练习形成可复查的学习闭环。
- 判断选点 / 最大独立集的适用条件与状态边界
- 围绕“没有上司的舞会”推导转移与计算顺序
- 用演示、复杂度分析和配套题目校验实现
本课目录 · 0 节
正在整理目录…
从一场不能同席的舞会说起
公司是一棵树：董事长在根，每个人往下带若干直接下属。现在办舞会，每个人来了会带来一份欢乐值。 只有一条规矩——任何人都不愿与自己的直接上司同场。要让到场的总欢乐值最大，该请谁？
用图论的话说：在树上选一个点集，使得没有任何一条边的两端同时被选（这样的点集叫「独立集」）， 并让选中点的权和最大。这就是最大权独立集。
先想想能不能贪心：按欢乐值从大到小挑，能选就选？会翻车。设董事长欢乐值 ，他有两个下属各 ， 两个下属又各带一个孙辈 。贪心先抢董事长（10），于是两个下属都不能选；孙辈可选，得 。 但只要放弃董事长、改选两个下属加两个孙辈，就是 ——贪心又输了。
那枚举每个点「选 / 不选」的所有组合呢？ 种， 直接爆炸。 问题的结构是树，而树天生适合把子树的答案往上合并——这正是树形 DP 的舞台。
状态与转移：这个点，选还是不选
定状态。对每个点 开两个状态，把「u 自己选没选」记进状态里：
读作： = u 不选时，以 u 为根的整棵子树能取到的最大权； = u 选时子树的最大权。 把状态开成两份，是为了让父亲知道「孩子到底选没选」——因为父子不能同时选，这个信息必须显式带上。
u 不选：它没占位，每个孩子 选不选都行，各自取更优的那个：
u 选：它占了位，所有孩子都不许选，只能取孩子的「不选」态，再加上 u 自己的权 ：
边界：叶子没有孩子，、。 答案在根：。
本质
把「u 选没选」压进状态，父子那条唯一的约束就变成了两条干净的求和公式； 的组合塌缩成每个点 的合并，总复杂度 。这套 是所有树形 DP 的第一块积木。
跟着算一遍
用一棵小树：根 （权 3）带两个孩子 （权 6）、（权 2）； 再带两个叶子 （权 4）、（权 7）。后序次序 ：
看 dp 自底向上长出来
- 来源参与当前转移的依赖状态
- 当前正在计算或观察的状态
- 确定 / 最优已进入当前最优解或确定结果
- 已处理已经扫描、当前不再活跃的状态
- 非法越界、冲突或不可达状态
翻个面：最小点覆盖，转移方向正好相反
换一个问题：树上放最少的士兵看守所有边——每条边至少有一端站着士兵（这叫最小点覆盖）。 状态还是 （u 不放 / 放），但转移和独立集恰好对称：
盯住 ：u 不放兵，那每条 的边就只能靠 c 那端守，于是孩子必须放（取 ）。 这与独立集「u 不选、孩子自由取 」正好反过来——独立集要「避免相邻」，点覆盖要「盯住每条边」。
常见陷阱：别把「孩子自由」照抄过来
写点覆盖时最容易犯的错，是把独立集的 直接搬来。u 不放兵，孩子就没有「自由」——边必须有人守，孩子被强制取 。看清「约束落在点上还是边上」，转移方向就不会写反。更复杂的「支配集」还要引入第三个状态，见 覆盖 / 支配 / 染色。
例题
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 6005;
vector<int> g[N]; // 邻接表：g[u] 存 u 的直接下属
int r[N]; // 每个人的欢乐值
int f[N][2]; // f[u][0/1]：u 不选/选时，u 子树的最大欢乐值
int fa[N]; // 记录父亲，用来找根
bool hasFa[N];
void dfs(int u) // 固定根，一遍后序 DFS
{
f[u][0] = 0; // 不选 u：先清零
f[u][1] = r[u]; // 选 u：先加上自己的欢乐值
for (int v : g[u]) // 逐个孩子合并
{
dfs(v); // ★先把孩子子树算完（后序）
f[u][0] += max(f[v][0], f[v][1]); // u 不选：孩子随意，各取较大
f[u][1] += f[v][0]; // u 选了：孩子必须都不选
}
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> r[i];
for (int i = 1; i < n; i++)
{
int l, k;
cin >> l >> k; // l 的上司是 k
g[k].push_back(l);
hasFa[l] = true;
}
int root = 1;
while (root <= n && hasFa[root]) root++; // 没有上司的那个人就是根
dfs(root);
cout << max(f[root][0], f[root][1]) << endl;
return 0;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 1505;
vector<int> g[N];
int f[N][2]; // f[u][0]：u 不放兵；f[u][1]：u 放兵
bool hasFa[N];
void dfs(int u)
{
f[u][0] = 0; // u 不放兵：它的每条边要靠孩子那端守
f[u][1] = 1; // u 放兵：+1 个士兵
for (int v : g[u])
{
dfs(v);
f[u][0] += f[v][1]; // ★u 不放 → 孩子必须放（否则边 u-v 没人看守）
f[u][1] += min(f[v][0], f[v][1]); // u 放了 → 孩子放不放都行，取较小
}
}
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
int u, cnt;
cin >> u >> cnt; // 洛谷本题为 0-based，读入时 +1 归一到 1-based
u++;
while (cnt--)
{
int v;
cin >> v;
v++;
g[u].push_back(v);
hasFa[v] = true;
}
}
int root = 1;
while (root <= n && hasFa[root]) root++;
dfs(root);
cout << min(f[root][0], f[root][1]) << endl;
return 0;
}