题目概述

BZOJ4182弱化版，原版是要求选出来的点是连通的（我不会），弱化版只需要满足儿子选了父亲必选。

解题报告

其实之前做过带依赖的一道题，但是并没有体积，所以依然可以用正常的树形DP做。

但这道题有体积，所以原先那种复杂度分析版的树形DP就会被cao。正确姿势是在DFS序上DP，定义 $f[i][j]$ 表示DFS序 $[1,i]$ 体积为 $j$ 的最优解，这样转移就只有两种：

1. $i$ 点选，那么转移到 $f[i+1][k]$ 。
2. $i$ 点不选，那么子树也没有选，转移到 $f[out[i]+1][k]$ 。

由于物品还有个系数，所以可以二进制拆分 $O(nmlog_2S)$ 或者单调队列（我不会）$O(nm)$ 。第一次写写了很久QAQ，详细看代码。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=4000,maxm=4000;

int n,m,w[maxn+5],p[maxn+5],s[maxn+5];
int E,lnk[maxn+5],son[maxn+5],nxt[maxn+5];
int ti,Lt[maxn+5],Rt[maxn+5],ID[maxn+5];
LL f[maxn+5][maxm+5];

#define Add(x,y) (son[++E]=(y),nxt[E]=lnk[x],lnk[x]=E)
void Dfs(int x) {ID[Lt[x]=++ti]=x;for (int j=lnk[x];j;j=nxt[j]) Dfs(son[j]);Rt[x]=ti;}
int main(){
    freopen("shop.in","r",stdin);freopen("shop.out","w",stdout);
    scanf("%d%d",&n,&m);for (int i=2,fa;i<=n;i++) scanf("%d",&fa),Add(fa,i);
    for (int i=1;i<=n;i++) scanf("%d%d%d",&p[i],&w[i],&s[i]);
    Dfs(1);memset(f,192,sizeof(f));LL INF=f[0][0];f[1][0]=0;
    for (int i=1,k=ID[i];i<=n;k=ID[++i]){
        for (int j=0;j<=m;j++) f[Rt[k]+1][j]=max(f[Rt[k]+1][j],f[i][j]);
        for (int j=m;~j;j--) if (j>=w[k]&&f[i][j-w[k]]>=0) f[i][j]=f[i][j-w[k]]+p[k]; else f[i][j]=INF;
        for (int t=(s[k]--,1);t<s[k];s[k]-=t,t<<=1)
            for (int j=m,W=t*w[k],P=t*p[k];j>=W;j--)
                f[i][j]=max(f[i][j],f[i][j-W]+P);
        if (s[k]) for (int j=m,W=s[k]*w[k],P=s[k]*p[k];j>=W;j--) f[i][j]=max(f[i][j],f[i][j-W]+P);
        for (int j=0;j<=m;j++) f[i+1][j]=max(f[i+1][j],f[i][j]);
    }
    n++;for (int j=1;j<=m;j++) f[n][j]=max(f[n][j],f[n][j-1]),j>1?printf(" %lld",f[n][j]):printf("%lld",f[n][j]);
    return puts(""),0;
}