P12444 [COTS 2025] 发好奖 / Hijerarhija
和树上背包很像，唯一区别在于必须分配 \(c_i\) 的空间才能产生价值。
如果按普通的分组背包来跑，值域是 \(nk\) 的，总时间 \(O(nk^2)\) 过不掉。为此我们尽可能避免合并泛化物品的过程。
一个很厉害的 trick 是在 dfs 序上进行 dp。即令 \(f[i][j]\) 为 dfs 序意义下前 \(i\) 个人，分配 \(j\) 的体积，最大价值。
则有转移：
-
不给 \(i\) 分配体积：\(f[i][j]\to f[i+siz_i][j]\)。
-
给 \(i\) 分配 \(1\) 的体积：\(f[i][j]\to f[i+1][j+1]\)。
-
给 \(i\) 分配 \(c_i\) 的体积：\(f[i][j]+p[i]\to f[i+1][j+c_i]\)。
点击查看代码
#include<bits/stdc++.h>
#define eb emplace_back
#define int long long
using namespace std;
inline void chmx(int &x,int y){x=max(x,y);}
const int N=5005,M=5005;
int ninf;
int n,m,sz[N],rk[N],tim,f[N][M],c[N],p[N],ans;
vector<int> G[N];
inline void dfs(int u){rk[++tim]=u,sz[u]=1;for(int i:G[u]){dfs(i);sz[u]+=sz[i];}
}
signed main(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);memset(f,-0x3f,sizeof f),ninf=**f;cin>>n>>m;for(int i=2,f;i<=n;i++){cin>>f;G[f].eb(i);}for(int i=1;i<=n;i++) cin>>p[i];for(int i=1;i<=n;i++) cin>>c[i];dfs(1);f[1][0]=0;for(int i=1;i<=n;i++){for(int j=0;j<=m;j++){if(f[i][j]==ninf) continue;int x=rk[i];chmx(f[i+sz[x]][j],f[i][j]);chmx(f[i+1][j+1],f[i][j]);if(j+c[x]<=m) chmx(f[i+1][j+c[x]],f[i][j]+p[x]);}}ans=ninf;for(int i=0;i<=m;i++) chmx(ans,f[n+1][i]);cout<<ans<<"\n";return 0;
}
另外这个 trick 也可以写普通树上背包，就是去掉分配 \(c_i\) 的情况而已。
相比分组写法不用写一坨上下界优化，细节少码量小。不知道为什么这么冷门。
嗯嗯。之后树形背包都写 dfs 序了（真的）。