AtCoder

Luogu

分析

考虑差分，则问题变为每次选择一棵子树，消耗 $\sum m_i$ 的材料，造出 $sz$ 个物品，且每棵不是原树的子树都只能选至多 $D$ 次。

令每棵子树的 $m_i$ 之和为其代价，$sz$ 为其收益，则相当于一个多重背包。

然而 $D$ 在 $10^9$ 级别，直接多重背包显然无法通过。

考虑一个错误的贪心：设 $w_i$ 为收益，$v_i$ 为代价，按 $\frac{w_i}{v_i}$ 排序并从大到小贪心选。

考虑什么时候这个贪心是对的。假设有两个物品 $i,j$ 满足 $\frac{w_i}{v_i}>\frac{w_j}{v_j}$，那么在收益相等（选了 $w_j$ 个 $i$，选了 $w_i$ 个 $j$）的情况下，选 $w_j$ 个 $i$ 显然会更优。从而在 $\frac{w_i}{v_i}$ 大的物品还能加的时候，$\frac{w_i}{v_i}$ 小的至多会选 $w_i-1$ 个。

所以我们只需要每种物品拿出 $\min\{n,D\}$ 个出来多重背包，剩下的部分贪心即可。

实现时求出 $dp_i$ 表示达到 $i$ 的代价最小需要的体积，然后枚举背包贡献的代价、剩下的贪心装满即可。多重背包部分可以二进制分组，也可以单调队列。

代码

// ===================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ===================================
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

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=50+10;

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

int n,X,d;
struct node { ll v; int w,id; } a[N];
int operator <(node a,node b) { return a.w*b.v>b.w*a.v; }
ll dp[N*N*N];

void dfs(int u) {
    a[u].w=1,a[u].id=u;
    for (int i=head[u];i;i=e[i].nxt)
        dfs(e[i].v),a[u].v+=a[e[i].v].v,a[u].w+=a[e[i].v].w;
}

int main() {
    n=read(),X=read(),d=read();
    a[1].v=read();
    for (int i=2;i<=n;++i)
        a[i].v=read(),addEdge(read(),i);
    dfs(1); int mx=n*n*n,L=min(n,d);
    memset(dp,0x3f,sizeof(dp)),dp[0]=0;
    for (int i=1;i<=n;++i) {
        int x=L;
        for (int j=0;1<<j<=x;++j) {
            int w=a[i].w*(1<<j); ll v=a[i].v*(1<<j);
            for (int k=mx;k>=w;--k) dp[k]=min(dp[k],dp[k-w]+v);
            x-=1<<j;
        }
        if (x) {
            int w=a[i].w*x; ll v=a[i].v*x;
            for (int j=mx;j>=w;--j) dp[j]=min(dp[j],dp[j-w]+v);
        }
    }
    sort(a+1,a+n+1);
    while (a[n].id!=1) --n;
    ll ans=0;
    for (int i=0;i<=mx;++i) {
        if (dp[i]>X) continue;
        ll w=i,v=dp[i];
        for (int j=1;j<n;++j) {
            ll c=min((ll)d-L,(X-v)/a[j].v);
            w+=c*a[j].w,v+=c*a[j].v;
        }
        ll c=(X-v)/a[n].v;
        w+=c*a[n].w,v+=c*a[n].v;
        ans=max(ans,w);
    }
    printf("%lld\n",ans);
    return 0;
}