arc096F

题目大意

题解

貌似之前杂题讲过，但是完全忘了

先假设n<=D，否则取个min之类的

首先显然可以差分后变成一次对子树操作，则变为二元组(vi,wi)表示代价为wi，贡献为vi，且除了1以外的子树最多选d个

考虑假的贪心：按照vi/wi从大到小排序，之后按顺序选

发现这样有个性质：当vi/wi>vj/wj时，有viwj>vjwi，即选了vi个j时可以用vj个i来替换，结果更优

由于v的上限是n，所以把约束放宽，只有当i的选择个数>D-n时i+1才能选超过n个

那么可以把每个i先提n个出来，这n个可以选任意个，之后剩下D-n个按顺序贪心，这样和原问题是等价的，因为最优方案一定可以被表示

dp算出提n个的答案，之后枚举状态贪心，注意状态数是n^3的，所以要用二进制优化，并且当选了整棵树时没有个数限制

时间O(n^4log)

code

#include <bits/stdc++.h>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define ll long long
//#define file
using namespace std;

struct type{ll v,w;} a[51];
ll f[125001],V,W,D,N,x,s,ans,Ans;
int fa[51],n,m,i,j,k,l;

bool cmp(type a,type b) {return a.v*b.w>b.v*a.w;}

int main()
{
	#ifdef file
	freopen("arc096F.in","r",stdin);
	#endif
	
	scanf("%d%lld%lld",&n,&x,&D),N=min(n,D),m=n*n*N;
	scanf("%lld",&a[1].w),a[1].v=1;
	fo(i,2,n) scanf("%lld%d",&a[i].w,&fa[i]),a[i].v=1;
	fd(i,n,2) a[fa[i]].w+=a[i].w,a[fa[i]].v+=a[i].v;
	
	memset(f,1,sizeof(f)),f[0]=0;
	sort(a+1,a+n+1,cmp);
	fo(i,1,n)
	{
		s=l=1;
		while (s<=N)
		{
			V=a[i].v*l,W=a[i].w*l;
			fd(k,m-V,0) f[k+V]=min(f[k+V],f[k]+W);
			l*=2,s+=l;
		}
		s=N-(s-l);
		V=a[i].v*s,W=a[i].w*s;
		fd(k,m-V,0) f[k+V]=min(f[k+V],f[k]+W);
	}
	
	fo(i,0,m)
	if (f[i]<=x)
	{
		Ans=i,s=x-f[i];
		fo(j,1,n)
		if ((D-N)<=s/a[j].w)
		{
			if (a[j].v<n)
			s-=a[j].w*(D-N),Ans+=a[j].v*(D-N);
			else
			{Ans+=(s/a[j].w)*a[j].v;s%=a[j].w;break;}
		}
		else
		{Ans+=(s/a[j].w)*a[j].v;s%=a[j].w;break;}
		
		ans=max(ans,Ans);
	}
	printf("%lld
",ans);
}