[总结]树形依赖背包的优化方法

树形背包依赖问题

转自学长

每个点有权值和体积，如果要选它就必须选它的父亲，问体积和≤m的情况下的最大点权和。

如果体积为1，直接做是 (n^2) 的。

否则是 (nm^2) 的。

我们可以求出这棵树的后序遍历，即先访问儿子再访问自己。

那么对于 (i) 这个点，它的子树是 (i) 之前连续的一段，且 (i) 是最后一个点。

枚举 (i) 选不选，如果选，那么从 (f[i-1]) 转移来，否则从 (f[i-sze[i]];copy) 来。

复杂度 (nm)，每个点都只做了一遍背包。

例题：JZOJ5661 药香沁鼻

裸

#include<cstdio>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#define N 5005
#define M 10005
using std::min;
using std::max;
using std::swap;
int sze[N];
int f[N][M];
int head[N];
int a[N],b[N];
int n,m,tot,cnt;
struct Edge{
int to,nxt;
}edge[N<<1];
void add(int x,int y){
edge[++cnt].to=y;
edge[cnt].nxt=head[x];
head[x]=cnt;
}
int getint(){
int x=0,f=0;char ch=getchar();
while(!isdigit(ch)) f|=ch=='-',ch=getchar();
while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return f?-x:x;
}
void dfs(int now){
sze[now]=1;
for(int i=head[now];i;i=edge[i].nxt){
int to=edge[i].to;
dfs(to);sze[now]+=sze[to];
}
int dfn=++tot;
for(int j=0;j<=m;j++){
if(j<a[now])
f[dfn][j]=f[dfn-sze[now]][j];
else
f[dfn][j]=max(f[dfn-sze[now]][j],f[dfn-1][j-a[now]]+b[now]);
}
}
signed main(){
n=getint(),m=getint();
for(int i=1;i<=n;i++){
a[i]=getint();
int x=getint();
if(x!=i) add(x,i);
b[i]=getint();
}
dfs(1);
printf("%dn",f[tot][m]);
return 0;
}