【Codeforces Round #419 (Div. 1)】Codeforces 815C Karen and Supermarket

可以发现依赖关系是一个树形结构，我们可以树形dp，对每个点记录$f[u][i]$和$g[u][i]$表示$u$的子树取$i$个结点，子树中可以有优惠券、不能有优惠券的最小花费，不难转移。
可以证明，复杂度是$O(n^2)$的。

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=5010,oo=0x3f3f3f3f;
vector<int> son[maxn];
int size[maxn],c[maxn],d[maxn],f[maxn][maxn],g[maxn][maxn],val[maxn],tf[maxn],tg[maxn],n,m,clo;
void dfs(int u)
{//printf("in:%d\n",u);int v;for (int i=2;i<=n;i++) f[u][i]=g[u][i]=oo;size[u]=1;f[u][1]=c[u]-d[u];g[u][1]=c[u];for (vector<int>::iterator it=son[u].begin();it!=son[u].end();++it){v=*it;dfs(v);for (int i=0;i<=size[u];i++){tf[i]=f[u][i];tg[i]=g[u][i];}for (int i=0;i<=size[u];i++)for (int j=1;j<=size[v];j++){g[u][i+j]=min(g[u][i+j],g[v][j]+tg[i]);f[u][i+j]=min(f[u][i+j],i?f[v][j]+tf[i]:oo);}size[u]+=size[v];}for (int i=1;i<=size[u];i++) f[u][i]=min(f[u][i],g[u][i]);//printf("out:%d %d\n",u,size[u]);
}
int main()
{//freopen("c.in","r",stdin);int x;scanf("%d%d",&n,&m);scanf("%d%d",&c[1],&d[1]);for (int i=2;i<=n;i++){scanf("%d%d%d",&c[i],&d[i],&x);son[x].push_back(i);}dfs(1);//printf("%d\n",clo);for (int i=n;;i--)if (f[1][i]<=m){printf("%d\n",i);return 0;}
}