Description
Input
Output
Sample Input
7 9
39 6
13 2
22 6
7 4
-19 5
28 6
-17 1
2 1
3 2
4 1
5 4
6 2
7 3
Sample Output
52
Data Constraint
Solution
这是一道经典的树形依赖DP（背包问题），即选取一个物品需要先选另一个物品。
设
F[i][j] 表示做到第i 点、已使用的费用为j 的最大价值。则显然有：
F[i][j]=max{F[son][j−p[i]]+v[i]} 转移即可，时间复杂度：
O(NM) 。
Code
#include<cstdio>
using namespace std;
const int N=2001;
int n,m,tot,ans;
int first[N],next[N<<1],en[N<<1];
int v[N],p[N],f[N][N*5];
inline int read()
{
int X=0,w=1; char ch=0;
while(ch<'0' || ch>'9') {if(ch=='-') w=-1;ch=getchar();}
while(ch>='0' && ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
return X*w;
}
inline int max(int x,int y)
{
return x>y?x:y;
}
inline void insert(int x,int y)
{
next[++tot]=first[x];
first[x]=tot;
en[tot]=y;
}
inline void dfs(int x,int y,int z)
{
if(z<=0) return;
for(int i=first[x];i;i=next[i])
if(en[i]!=y)
{
for(int j=z-p[en[i]];j>=0;j--) f[en[i]][j]=f[x][j];
dfs(en[i],x,z-p[en[i]]);
for(int j=z;j>=p[en[i]];j--) f[x][j]=max(f[x][j],f[en[i]][j-p[en[i]]]+v[en[i]]);
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) v[i]=read(),p[i]=read();
for(int i=1;i<n;i++)
{
int x=read(),y=read();
insert(x,y);
insert(y,x);
}
dfs(1,0,m);
for(int i=m-p[1];i;i--) ans=max(ans,f[1][i]);
if(m>=p[1]) ans+=v[1];
printf("%d",ans);
return 0;
}