给定一棵有根树，记$f_{i}$表示$i$的父亲，每一个点有一个代价$c_{i}$
给定常数$D$和$X$，再给每个点赋一个权值$v_{i}$（$v_{i}ge 0$），满足以下条件下最大化$sum_{i=1}^{n}v_{i}$
条件：1.$forall 2le ile n,v_{f_{i}}le v_{i}le v_{f_{i}}+D$；2.$sum_{i=1}^{n}c_{i}v_{i}le X$
$2le nle 50$，$1le f_{i}<i$，$0le Dle 10^{9}$，$1le X,c_{i}le 10^{9}$
构造$d_{i}=v_{i}-v_{f_{i}}$（特别的$d_{1}=v_{1}$），那么$v_{i}=d_{i}+v_{f_{i}}=...=sum_{j为i祖先}d_{j}$
考虑每一个点的贡献，则有$sum_{i=1}^{n}v_{i}=sum_{i=1}^{n}d_{i}sz_{i}$和$sum_{i=1}^{n}c_{i}v_{i}=sum_{i=1}^{n}d_{i}sum_{i}$（其中$sz_{i}$为以$i$为根的子树大小，$sum_{i}$为以$i$为根子树中所有$c_{i}$的和）
可以看作一个背包，$n$个物品质量为$sum_{i}$，价值为$sz_{i}$，数量限制为$D$
先将所有物品按照“性价比”$frac{sz_{i}}{sum_{i}}$从大到小排序，则若存在$x<y$满足$d_{x}+sz_{y}le D$且$d_{y}ge sz_{x}$，那么不妨令$d'_{y}=d_{y}-sz_{x}$且$d'_{x}=d_{x}+sz_{y}$，显然质量之和不变且价值不减少，因此最优解中必然不存在这类点对
由于$sz_{i}le n$，将条件收缩为存在$x<y$满足$d_{x}+nle D$且$d_{y}ge n$
进一步的，将最终答案中的$d_{i}$分为三类：1.$D-n<d_{i}le D$；2.$nle d_{i}le D-n$；3.$0le d_{i}<n$，根据上述结论，任意第$i$类一定要在任意第$i+1$类前，且第2类数量不超过1（形象地，即构成了111……2333……）
对于第1类，转化为$D-n+1+d'_{i}$；对于第2类，转化为$d'_{i}+lfloorfrac{d_{i}}{n} floor n$，则都有$0le d'_{i}<n$
先对$d'_{i}$背包，由于价值范围为$o(n^{3})$，那么令$f[i][j]$表示前$i$个物品，价值和为$j$的最小质量来dp即可，时间复杂度为$o(n^{4}ln n)$或$o(n^{4})$（前者利用物品数量小于$frac{n^{3}}{sz_{i}}$，后者用单调队列
枚举$sum_{i=1}^{n}d'_{i}sz_{i}$（共$o(n^{3})$种），根据第$i$类要在第$i+1$类前的性质，对于剩下的部分贪心即可
（过程一眼看可能会有点假，注意$d'_{i}$是由$d_{i}$强制构造出来的，然后贪心根据的是结论）
特别的，对于$sz_{x}=n$这个位置（即原来的根），其没有数量限制，以第2类的方式构造$d'_{i}$，然后其贪心时没有上限
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 105 4 #define ll long long 5 struct ji{ 6 int nex,to; 7 }edge[N]; 8 int E,n,m,d,x,head[N],id[N],sz[N],f[2][N*N*N]; 9 ll ans,sum[N]; 10 bool cmp(int x,int y){ 11 return sz[x]*sum[y]>sz[y]*sum[x]; 12 } 13 void add(int x,int y){ 14 edge[E].nex=head[x]; 15 edge[E].to=y; 16 head[x]=E++; 17 } 18 void dfs(int k){ 19 sz[k]=1; 20 for(int i=head[k];i!=-1;i=edge[i].nex){ 21 dfs(edge[i].to); 22 sz[k]+=sz[edge[i].to]; 23 sum[k]+=sum[edge[i].to]; 24 } 25 } 26 int main(){ 27 scanf("%d%d%d%lld",&n,&m,&d,&sum[1]); 28 memset(head,-1,sizeof(head)); 29 for(int i=2;i<=n;i++){ 30 scanf("%lld%d",&sum[i],&x); 31 add(x,i); 32 } 33 dfs(1); 34 for(int i=1;i<=n;i++)id[i]=i; 35 sort(id+1,id+n+1,cmp); 36 int mm=n*n*n; 37 for(int i=1;i<=mm;i++)f[0][i]=m+1; 38 for(int i=1;i<=n;i++){ 39 int p=(i&1); 40 for(int j=0;j<=mm;j++){ 41 f[p][j]=m+1; 42 for(int k=0;(k<=min(n,d))&&(k*sz[id[i]]<=j);k++) 43 f[p][j]=min((ll)f[p][j],f[p^1][j-k*sz[id[i]]]+k*sum[id[i]]); 44 } 45 } 46 for(int i=0;i<=mm;i++) 47 if (f[(n&1)][i]<=m){ 48 int s=m-f[(n&1)][i]; 49 ll tot=i; 50 for(int j=1;j<=n;j++) 51 if ((id[j]==1)||(sum[id[j]]*(d-n)>s)){ 52 tot+=1LL*sz[id[j]]*(s/sum[id[j]]); 53 s-=sum[id[j]]*(s/sum[id[j]]); 54 } 55 else{ 56 if (d<n)continue; 57 tot+=1LL*sz[id[j]]*(d-n); 58 s-=sum[id[j]]*(d-n); 59 } 60 ans=max(ans,tot); 61 } 62 printf("%lld",ans); 63 }