Codeforces

Luogu

分析

感觉是个比较简单的题。

设 $dp_{u,i,0/1}$ 表示以 $u$ 为根的子树，选了 $i$ 个物品，物品 $u$ 用/不用消费券的最小花费。

边界为 $dp_{u,0,0}=0,dp_{u,1,0}=c_u,dp_{u,1,1}=c_u-d_u$，转移就是树上的分组背包。

答案就是最大的使得 $\min\left\{dp_{1,i,0},dp_{1,i,1}\right\}\leq b$ 的 $i$。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline void chkmin(int& x,int y) { if (y<x) x=y; }
inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=5000+10;

int n,b,c[N],d[N];

struct edge { int v,nxt; } e[N<<1];
int head[N];
inline void addEdge(int u,int v) {
    static int cnt=0;
    e[++cnt]=(edge){v,head[u]},head[u]=cnt;
}

int sz[N],dp[N][N][2],tmp[N][2];
inline void dfs(int u,int fa) { sz[u]=1;
    dp[u][0][0]=0,dp[u][1][0]=c[u],dp[u][1][1]=c[u]-d[u];
    for (re int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v; if (v==fa) continue;
        dfs(v,u);
        memcpy(tmp,dp[u],sizeof(tmp));
        for (re int j=0;j<=sz[u];++j)
            for (re int k=0;k<=sz[v];++k) {
                chkmin(tmp[j+k][0],dp[u][j][0]+dp[v][k][0]);
                chkmin(tmp[j+k][1],dp[u][j][1]+dp[v][k][0]);
                chkmin(tmp[j+k][1],dp[u][j][1]+dp[v][k][1]);
            }
        memcpy(dp[u],tmp,sizeof(tmp));
        sz[u]+=sz[v];
    }
}

int main() {
    n=read(),b=read();
    for (re int i=1;i<=n;++i) {
        c[i]=read(),d[i]=read();
        if (i>1) addEdge(read(),i);
    }
    memset(dp,0x3f,sizeof(dp)); dfs(1,0);
    int ans=n;
    for (;ans;--ans)
        if (dp[1][ans][0]<=b||dp[1][ans][1]<=b) break;
    printf("%d\n",ans);
    return 0;
}