[文章目录]
Description
约翰的N(1≤N≤500)头奶牛打算组队去参加一个世界级的产奶比赛，她们很清楚其他队的实力，也就是说，她们派出的队只要能产出至少X(I≤X≤1000000)加仑牛奶，就能赢得这场比赛。每头牛都能为集体贡献一定量的牛奶，数值在-10000到10000之间（有些奶牛总是想弄翻装着其他奶牛产的奶的瓶子）．
她们希望在选出的队伍里能有尽可能多的牛来自同一个家庭，也就是说，有尽可能多对的牛有直系血缘关系（当然，这支队伍必须能产出至少X加仑牛奶） 约翰熟知所有奶牛之间的血缘关系．现在他想知道，如果在保证一支队伍能赢得比赛的情况下，队伍中最多能存在多少对直系血缘关系。
树形背包，下标为直系个数，表示最多的产奶量。注意DP的时候的先后顺序。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,w[510];
int head[510],nxt[510],to[510],cnt;
inline void add(int x,int y)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt;
}
inline int Max(int x,int y){return x>y ? x:y;}
int f[510][510],g[510][510],siz[510];
void dfs(int x,int y)
{
f[x][0]=w[x]; g[x][0]=0;
for(int i=head[x];i;i=nxt[i])
{
dfs(to[i],x);
for(int j=siz[x];~j;--j)
for(int k=siz[to[i]];~k;--k)
{
f[x][j+k+1]=Max(f[x][j+k+1],f[x][j]+f[to[i]][k]);
f[x][j+k]=Max(f[x][j+k],f[x][j]+g[to[i]][k]);
g[x][j+k]=Max(g[x][j+k],g[x][j]+Max(g[to[i]][k],f[to[i]][k]));
}
siz[x]+=(siz[to[i]]+1);
}
}
int main()
{
scanf("%d%d",&n,&m); int x;
for(int i=1;i<=n;++i)
{
scanf("%d%d",w+i,&x);
add(x,i);
}
memset(f,0xef,sizeof f); memset(g,0xef,sizeof g);
f[0][0]=g[0][0]=0;
for(int i=head[0];i;i=nxt[i])
{
dfs(to[i],0);
for(int j=siz[0];~j;--j)
for(int k=siz[to[i]];~k;--k)
f[0][j+k]=Max(f[0][j+k],f[0][j]+Max(f[to[i]][k],g[to[i]][k]));
siz[0]+=siz[to[i]];
}
for(int i=siz[0];i>=0;--i)
if(f[0][i]>=m)
{
printf("%d",i);
return 0;
}
puts("-1");
return 0;
}