1 题意
职员的上下级关系构成一棵有根树。每个职员有一个快乐值,选择若干职员参加舞会,使快乐值之和最大。一个职员与其直接上司不能同时参加。
将职员看作节点,上下级关系看作边,就得到:在树上选择若干节点,使任意一条边的两个端点不同时被选,并最大化点权之和。这称为树上的最大权独立集。
限制只发生在相邻节点之间。上司和下属的下属可以同时参加;也允许一个职员都不邀请,此时总快乐值为
原题保证
2 子树划分
枚举每个节点选或不选,共有
利用树的结构,可以把问题拆成各个孩子的子树。但不能直接把每棵子树的最优值相加:孩子子树的最优方案可能选择了孩子,这会限制父节点能否选择。
对于一棵以
确定
图中的限制只针对孩子节点,不是禁止选择孩子的整棵子树。
3 状态定义
记
| 状态 | 含义 |
|---|---|
| 在 |
|
| 在 |
两个状态都要求子树内部满足相邻节点不能同时选择。它们只规定
不能只保存
4 转移方程
设
4.1 选择 u
选择
这里的
4.2 不选 u
不选
不选父节点,不代表必须选择孩子。 孩子不选时,可能从更深的后代中取得更大收益。
公式中的两种运算各有含义:同一棵孩子子树的两种选择取 max,不同孩子子树的贡献用加法合并。
4.3 正确性
固定
反过来,为每个孩子取到对应的最优方案。不同孩子子树之间没有边,它们与
从叶子开始归纳,每个节点的两个状态均正确,最终便能得到整棵树的最优值。
5 初值与答案
尚未合并孩子时,先令:
随后逐个加入孩子子树的贡献。叶子没有孩子,这两个值就是最终结果。
即使
设根为
不需要再对所有子树取最大值:根的子树已经包含整棵树。
6 手算示例
以下是自拟示例。根为
按先孩子、后父亲的顺序计算:
| 节点 |
快乐值 |
不选 |
选择 |
|---|---|---|---|
| 3 | 7 | 0 | 7 |
| 4 | -2 | 0 | -2 |
| 5 | 3 | 0 | 3 |
| 6 | 8 | 0 | 8 |
| 1 | 4 | 7 | 4 |
| 2 | 5 | 11 | 5 |
| 7 | 6 | 18 | 24 |
例如,节点
根的两个状态为:
答案为
示例输入输出
输入:
7
4
5
7
-2
3
8
6
1 7
2 7
3 1
4 1
5 2
6 2
输出:
24
7 代码实现
输入的每对 child parent 表示后者是前者的直接上司。因此只保存从上司指向下属的边;没有上司的节点是根,编号不一定为
在 dfs(u) 中先设置初值,再对每个孩子执行 dfs(v),返回后合并它的两个状态。递归从根向下访问,状态按孩子先于父亲的后序依赖计算。
这里一次调用同时计算两个状态,每个节点只访问一次,不需要另设记忆化数组。单向存储孩子也避免了返回父节点,不需要访问标记。
#include <bits/stdc++.h>
using namespace std;
const int maxn = 6000 + 5;
vector<int> g[maxn]; // g[u] 只保存 u 的直接下属
int happy[maxn], f[maxn][2];
bool has_parent[maxn];
void dfs(int u) {
f[u][0] = 0; // 不选 u,先不计入任何孩子子树的贡献
f[u][1] = happy[u]; // 选 u,先计入 u 自己的快乐值
for (int v : g[u]) {
dfs(v); // 先求出孩子子树的两个状态,再合并到 u
f[u][0] += max(f[v][0], f[v][1]); // u 不选,v 可以选或不选
f[u][1] += f[v][0]; // u 选了,v 只能不选
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
for (int u = 1; u <= n; ++u) cin >> happy[u];
for (int i = 1; i < n; ++i) {
int child, parent;
cin >> child >> parent; // 输入顺序:下属、直接上司
g[parent].push_back(child);
has_parent[child] = true;
}
int root = 1;
while (has_parent[root]) ++root; // 唯一没有上司的职员是根
dfs(root);
cout << max(f[root][0], f[root][1]) << '\n';
return 0;
}
总快乐值不超过 int 即可。每个节点初始化一次,每条父子边合并一次,时间复杂度为
以子树为子问题,记录子树根与外部有关的状态;先求孩子,再按父子限制合并。本题只需区分根选或不选。换一道题时,应重新判断父节点需要从孩子子树中知道哪些信息。
8 相关题解
暂无相关题解