【jzoj5344】【NOIP2017模拟9.3A组】【摘果子】【树型依赖背包】

description

solution

直接树型依赖背包没什么好说的。

code

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define LF double
#define LL long long
#define ULL unsigned int
#define fo(i,j,k) for(int i=j;i<=k;i++)
#define fd(i,j,k) for(int i=j;i>=k;i--)
#define fr(i,j) for(int i=begin[j];i;i=next[i])
using namespace std;
int const mn=2000+2,mm=4000+2,inf=1e9+7;
int n,m,v[mn],p[mn],gra,begin[mn],to[mm],next[mm],size[mn],a[mn],f[mn][mn];
void insert(int u,int v){

to[++gra]=v;

next[gra]=begin[u];

begin[u]=gra;
}
void dfs(int p,int q){

a[++a[0]]=p;

size[p]=1;

fr(i,p)if(to[i]!=q){

dfs(to[i],p);

size[p]+=size[to[i]];

}
}
int main(){

freopen("d.in","r",stdin);

freopen("d.out","w",stdout);

scanf("%d%d",&n,&m);

fo(i,1,n)scanf("%d%d",&v[i],&p[i]);

fo(i,1,n-1){

int u,v;

scanf("%d%d",&u,&v);

insert(u,v);

insert(v,u);

}

dfs(1,0);

fo(i,0,n+1)fo(j,0,m)f[i][j]=-inf;

f[1][0]=0;

fo(i,1,n){

int q=a[i];

fo(j,0,m){

if(j+p[q]<=m){

f[i+1][j+p[q]]=max(f[i+1][j+p[q]],f[i][j]+v[q]);

f[i+size[q]][j+p[q]]=max(f[i+size[q]][j+p[q]],f[i][j]+v[q]);


}

f[i+size[q]][j]=max(f[i+size[q]][j],f[i][j]);

}

}

int ans=0;

fo(j,0,m)ans=max(ans,f[n+1][j]);

printf("%d",ans);

return 0;
}

最后

以上就是刻苦音响为你收集整理的【jzoj5344】【NOIP2017模拟9.3A组】【摘果子】【树型依赖背包】的全部内容，希望文章能够帮你解决【jzoj5344】【NOIP2017模拟9.3A组】【摘果子】【树型依赖背包】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。