http://codeforces.com/problemset/problem/816/E

Solution:

完了,原来我原来写的都是假的sz优化树D

好啊,如下为真真的板子:

#include
#include
#include
#include
#include
using namespace std;
const int MAXN=5000;
const int MAXM=10000;
int n,b,c[MAXN+10],d[MAXM+10];
int fir[MAXN+10],nxt[MAXM+10],to[MAXM+10],tot;
void adde(int u,int v){to[++tot]=v;nxt[tot]=fir[u];fir[u]=tot;}
int f[MAXN+10][MAXN+10],g[MAXN+10][MAXN+10],sz[MAXN+10];
void dfs(int u)
{
    f[u][0]=g[u][0]=0;
    for(int e=fir[u],v;(v=to[e]);e=nxt[e])
    {
        dfs(v);
        for(int i=sz[u];i>=0;--i)
            for(int j=sz[v];j;--j)
                f[u][i+j]=min(f[u][i+j],f[u][i]+f[v][j]),g[u][i+j]=min(g[u][i+j],g[u][i]+g[v][j]);
        sz[u]+=sz[v];
    }
    ++sz[u];
    for(int i=sz[u];i;--i)f[u][i]=f[u][i-1]+c[u]-d[u],g[u][i]=min(g[u][i],g[u][i-1]+c[u]);
    for(int i=sz[u];i;--i)f[u][i]=min(f[u][i],g[u][i]);
}
int main()
{
    scanf("%d%d",&n,&b);memset(f,0x3f,sizeof f);memset(g,0x3f,sizeof g);
    for(int i=1,fa;i<=n;++i)
    {
        scanf("%d%d",c+i,d+i);
        if(i>1){scanf("%d",&fa);adde(fa,i);}
    }
    dfs(1);
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        if(f[1][i]<=b)ans=i;
        else break;
    }
    printf("%d",ans);
    return 0;
}