【NOIP2017模拟9.3A组】摘果子

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

Solution

就是树上背包问题，有一个很经典的做法
按照dfs序反着来dp，那么f[i][j]表示的就是dfs序为i的点，受了j的毒的值
如果i这个点选，那么f[i][j]可以从f[i+1][j-p[i]]转移过来
否则可以从f[跨过i这个子树的下一个值][j]转移过来
为什么是正确的呢？
显然只选子树或只选兄弟是正确的
但是又要选子树又要选兄弟呢？
会发现到我子树的dfs最大的一个点的时候，它会将它+1的位置转移过来，也就是把兄弟转移了过来
那么又选子树又选兄弟就包含在选子树中了

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
#define N 20100
using namespace std;
int n,m,a[N],b[N],f[4050][4050],last[N],next[N],to[N],tot=0,dfn[N],ls[N],c[N];
void putin(int x,int y)
{
    next[++tot]=last[x];last[x]=tot;to[tot]=y;
}
void dg(int x)
{
    dfn[x]=++tot;c[tot]=x;
    for(int i=last[x];i;i=next[i])
    {
        if(dfn[to[i]]) continue;
        dg(to[i]);
    }
    ls[x]=tot;
}
int main()
{
    scanf("%d%d",&n,&m);
    fo(i,1,n) scanf("%d%d",&a[i],&b[i]);
    fo(i,1,n-1)
    {
        int x,y;scanf("%d%d",&x,&y);
        putin(x,y);putin(y,x);
    }
    tot=0;
    dg(1);
    fd(i,n,1)
    {
        fo(j,0,m)
        {
            if(j>=b[c[i]])f[i][j]=max(f[i][j],f[i+1][j-b[c[i]]]+a[c[i]]);
            f[i][j]=max(f[i][j],f[ls[c[i]]+1][j]);
        }
    }
    int ans=0;
    fo(i,0,m) ans=max(ans,f[1][i]);
    printf("%d",ans);
}