题解：P2014 CTSC 1997 选课

lalaji2010 · 2024-08-28 08:48:29 · 题解

P2014 [CTSC1997] 选课

~~题解区一堆 dalao 泛化物品优化直接用，是不是只有我这种蒟蒻根本看不懂 qaq。~~

本文讲得比较详细，只要耐心读下去再稍加理解应该可以读懂。

这题做了很久，非常好的一道题目。

这是一道经典的多叉树上资源分配问题，又称树形背包问题。

首先，二叉树上资源分配问题上个题就已经会做了，所以这道题可以多叉转二叉再左右儿子枚举分配数量记忆化一下来做。

但是这里放这道题的初衷还是为了介绍一下树形背包及其优化。

Part1 n,m \leq 300

有依赖关系的结构求固定个数元素最大和。可以考虑将依赖结构表现为一棵树，b 依赖于 a，则令 a 作为 b 的父亲，这样只需要做到求和的时候 a 不选 b 也不能选就好了。

建好之后是一个森林，考虑建立超级源点，将无依赖的结点作为超级源点的儿子，超级源点本身价值设为 0，这样选 m+1 个点即可。

设 dp[u][i][j] 表示从以 u 为根节点的子树的前 i 个孩子中选了 j 个结点的收益最大值。

当求解完 u 的第 k 个孩子 v，考虑状态转移的时候，你会发现这其实是一个 01 背包问题（每棵子树选或不选），不同的是当前子结点 v 的子树里的选择的元素个数即重量是可以变化的（枚举一下怎么变的不就好了吗），令 numv 表示 v 的最后一个儿子的编号（即儿子个数），tot 枚举 u 的前 k 个子树内选择的结点个数，sumk 枚举子树 v 内选择的结点个数，1 \leq tot \leq m,0 \leq sumk < tot，sumk<tot 的原因是 u 结点本身要选，v 内至多只能再选 tot-1 个结点。于是就有：

dp[u][k][tot]=\max(dp[u][k][tot],dp[u][k-1][tot-sumk]+dp[v][numv][sumk])

容易发现其实也可以像 01 背包一样（用一个不用滚动的滚动数组）压掉第二维（前 k-1 个的状态在 k-1 位置的 dp[] 数组中汇总），决策第 k 个儿子时只需要从大到小来枚举 tot 就可以调用 k-1 的状态了。

时间复杂度 O(nm^2)，发现能够通过本题。

代码应该是相当好懂的。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[305][305];
vector<int> e[305];
void dfs(int u,int fa){
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa) continue;
        dfs(v,u);
        for(int j=m;j>0;j--){
            for(int k=0;k<j;k++){
                dp[u][j]=max(dp[u][j],dp[u][j-k]+dp[v][k]);
            }
        }
    }
}
int main(){
    cin>>n>>m;
    m++;
    for(int i=1;i<=n;i++){
        int u=0;
        cin>>u>>dp[i][1];
        e[u].push_back(i);
        e[i].push_back(u); 
    }
    dfs(0,-1);
    printf("%d",dp[0][m]);
    return 0;
}

但是，我们怎么能把~~打一个暴力，切一道水题~~ O(nm^2) 作为目标呢，应当思考一些更 NB 的算法以更优秀的时间复杂度通过本题。

Part2 n,m \leq 5000

我们需要时间复杂度 O(nm) 的算法。

这里介绍一种树形背包的常用优化——泛化物品优化。

泛化物品：同一个物品，给它准备的重量限制不同，其价值也不同。来看一看怎么做的。

下文所说的子树不包含其根结点。

肯定是状态设得好，~~AC 没烦恼~~让其转移更便捷，设 dp[u][i] 表示在根节点与 u 的路径之外的且 dfs 序先于 u 的“旁路点”中以及 u 的子树内共选了 i 个点的最大和（这里 dp[u][i] 的概念在访问不同子结点时不同，u 的一个子结点 v 访问到的应该是在其前面遍历的子树及 u 的旁路点（它们都是 v 的旁路点）中选 i 个的最大值。本来是应该多开一维的，但是像 01 背包那样直接优化掉了；只有比 u 晚遍历且不在 u 子树内时访问它的值才是指整棵子树）。

我们就把 dfs 序先于 u 的结点分成了两类：若要选 u，则处于到根结点的路径上的结点必须选，其余的点可选可不选。

一个结点 v 的 dp[v][i] 可能来自于哪呢？

可以是其父亲 u 传下来的 dp[u][i]，表示先于 v 遍历的兄弟结点和 u 的旁路点里选 i 个再选上 v（v 自己一定不是自己的旁路点）即：
dp[v][i]=dp[u][i]+val[v]
也可以是选上 v 的某个儿子 w 然后让 w 再选 i-1 个其旁路点和子树内的点（先于它遍历的兄弟结点也是其旁路点！），共选了 i 个 v 的子树内的点和 v 的旁路点。对于 w 以后的每个儿子，w 的贡献都是应当被他们考虑在内的（并在上面进行背包问题类似的累加操作）。说白了，将子结点 w 的值尝试与前面的子结点（或旁路点）的值作背包，将 w 得到的答案一律保存到父亲 v 中，方便爷爷 u 和后面遍历兄弟取用，有：

dp[u][i]=\max(dp[u][i],dp[v][i-1])

在每一个父子结点块之间做的操作完全是基于背包的思想，只是利用了一些树形结构的特性，正确性显然。

子结构的问题会做了，我们整个问也就会做了，时间复杂度 O(nm)。

非常神奇地减掉了一层无用的状态枚举。

这道题同时告诉我们：

按照子树的遍历顺序，可以将根结点的值不断更新，从而起到压掉 dp 数组一维的作用。
状态的设计是动态规划中最为关键的一环。

如果还有不懂的可以看一下代码感性理解一下。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int n,m;
int dp[5005][5005];
int c[5005];
vector<int> e[5005];
void dfs(int u,int fa){
    for(int i=0;i<e[u].size();i++){
        int v=e[u][i];
        if(v==fa) continue;
        for(int j=0;j<=m;j++) dp[v][j]=max(dp[v][j],dp[u][j]+c[v]);//u 对 v 的贡献
        dfs(v,u);
        for(int j=1;j<=m;j++) dp[u][j]=max(dp[u][j],dp[v][j-1]);
        //v 对 u 的贡献，等同于将 v 视为后面访问到 dp[u][i] 的值里 i 的一部分
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int u=0;
        cin>>u;
        e[u].push_back(i);
        e[i].push_back(u); 
        cin>>c[i];
    }
    c[0]=0;
    dfs(0,-1);
    printf("%d",dp[0][m]);//超级源点到根节点（自己）之外的所有点选了 m 个的最大和
    return 0;
}