没有上司的舞会

1 题意

题目:luogu P1352: 没有上司的舞会。

职员的上下级关系构成一棵有根树。每个职员有一个快乐值,选择若干职员参加舞会,使快乐值之和最大。一个职员与其直接上司不能同时参加。

将职员看作节点,上下级关系看作边,就得到:在树上选择若干节点,使任意一条边的两个端点不同时被选,并最大化点权之和。这称为树上的最大权独立集。

限制只发生在相邻节点之间。上司和下属的下属可以同时参加;也允许一个职员都不邀请,此时总快乐值为 00。

原题保证 1≤n≤60001\le n\le6000、−128≤hu≤127-128\le h_u\le127,其中 huh_u 表示节点 uu 的快乐值。

2 子树划分

枚举每个节点选或不选,共有 2n2^n 种方案。直接比较相邻节点的快乐值也不够:一个上司的快乐值为 66,两个直接下属的快乐值分别为 4,54,5,选择上司就会错过总和为 99 的方案。

利用树的结构,可以把问题拆成各个孩子的子树。但不能直接把每棵子树的最优值相加:孩子子树的最优方案可能选择了孩子,这会限制父节点能否选择。

对于一棵以 uu 为根的子树,外部只通过 uu 与它相连。 父节点只需要知道 uu 有没有选,不必知道子树内部选了哪些节点。因此,为每棵子树分别保留“根不选”和“根选择”两个最优值。

确定 uu 的状态后,各个孩子子树之间没有边,也就没有相互限制,可以分别求最优值后相加。

选择 u 时每个孩子必须不选;不选 u 时每个孩子可以分别选择选或不选,各自的后代仍由子树状态处理

图中的限制只针对孩子节点,不是禁止选择孩子的整棵子树。

3 状态定义

记 TuT_u 为以 uu 为根的子树,定义:

状态 含义
f[u][0]f[u][0] 在 TuT_u 内选择节点,且不选 uu 时的最大快乐值之和
f[u][1]f[u][1] 在 TuT_u 内选择节点,且选择 uu 时的最大快乐值之和

两个状态都要求子树内部满足相邻节点不能同时选择。它们只规定 uu 的选择,不规定父节点的选择,也不包含子树外的快乐值。

不能只保存 max⁡(f[u][0],f[u][1])\max(f[u][0],f[u][1]):如果最大值来自选择 uu,父节点被选时,这个方案就不能使用。保留两类状态,才能为父节点提供合法的选择。

4 转移方程

设 C(u)C(u) 为 uu 的所有孩子组成的集合。

4.1 选择 u

选择 uu 后,每个孩子 vv 都不能选,只能贡献 f[v][0]f[v][0]。再加上 uu 自己的快乐值:

f[u][1]=hu+∑v∈C(u)f[v][0]. f[u][1]=h_u+\sum_{v\in C(u)}f[v][0].

这里的 f[v][0]f[v][0] 仍然允许选择 vv 的孩子,所以不需要再单独枚举孙子。

4.2 不选 u

不选 uu,每个孩子 vv 可以选,也可以不选。各棵子树分别取较优值:

f[u][0]=∑v∈C(u)max⁡(f[v][0],f[v][1]). f[u][0]=\sum_{v\in C(u)}\max\bigl(f[v][0],f[v][1]\bigr).

不选父节点,不代表必须选择孩子。 孩子不选时,可能从更深的后代中取得更大收益。

公式中的两种运算各有含义:同一棵孩子子树的两种选择取 max,不同孩子子树的贡献用加法合并。

4.3 正确性

固定 uu 选或不选后,上述转移恰好列出了每个孩子允许的状态。任意合法方案在孩子子树中的部分,都不会超过对应状态的最优值,所以总收益不会超过转移结果。

反过来,为每个孩子取到对应的最优方案。不同孩子子树之间没有边,它们与 uu 之间也满足限制,合并后就是合法方案,恰好达到转移结果。

从叶子开始归纳,每个节点的两个状态均正确,最终便能得到整棵树的最优值。

5 初值与答案

尚未合并孩子时,先令:

f[u][0]=0,f[u][1]=hu. f[u][0]=0,\qquad f[u][1]=h_u.

随后逐个加入孩子子树的贡献。叶子没有孩子,这两个值就是最终结果。

即使 hu<0h_u<0,也不能把 f[u][1]f[u][1] 改为 00,因为这个状态要求必须选择 uu。不选任何节点的方案由 f[u][0]f[u][0] 保留。全树快乐值都为负时,最终答案为 00。

设根为 rootroot。根既可以选,也可以不选,因此答案为:

max⁡(f[root][0],f[root][1]). \max\bigl(f[root][0],f[root][1]\bigr).

不需要再对所有子树取最大值:根的子树已经包含整棵树。

6 手算示例

以下是自拟示例。根为 77,节点内是编号,旁边标注快乐值;实心节点表示一组最优选择。

根为 7 的七节点树,选择节点 7、3、5、6,快乐值之和为 24

按先孩子、后父亲的顺序计算:

节点 uu 快乐值 huh_u 不选 f[u][0]f[u][0] 选择 f[u][1]f[u][1]
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

例如,节点 11 不选时,两个孩子分别贡献 max⁡(0,7)\max(0,7) 与 max⁡(0,−2)\max(0,-2),得到 f[1][0]=7f[1][0]=7;选择节点 11 时,两个孩子都不选,得到 f[1][1]=4f[1][1]=4。

根的两个状态为:

f[7][0]=max⁡(7,4)+max⁡(11,5)=18,f[7][1]=6+7+11=24. \begin{aligned} f[7][0]&=\max(7,4)+\max(11,5)=18,\\ f[7][1]&=6+7+11=24. \end{aligned}

答案为 2424,选择节点 7,3,5,67,3,5,6。根与孙子可以同时选择,而快乐值为负的节点 44 不必选择。

示例输入输出

输入:

7
4
5
7
-2
3
8
6
1 7
2 7
3 1
4 1
5 2
6 2

输出:

24

7 代码实现

输入的每对 child parent 表示后者是前者的直接上司。因此只保存从上司指向下属的边;没有上司的节点是根,编号不一定为 11。

在 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;
}

总快乐值不超过 6000×1276000\times127,原题使用 int 即可。每个节点初始化一次,每条父子边合并一次,时间复杂度为 O(n)O(n)。邻接表、状态数组与最坏深度为 nn 的递归栈共占 O(n)O(n) 空间。

说明树形DP的基本步骤

以子树为子问题,记录子树根与外部有关的状态;先求孩子,再按父子限制合并。本题只需区分根选或不选。换一道题时,应重新判断父节点需要从孩子子树中知道哪些信息。

8 相关题解

暂无相关题解