Description

[USACO06MAR] Milk Team Select G

【题目描述】

Farmer John 的 $N(1 \le N \le 500)$ 头奶牛打算参加一场世界级的产奶比赛 （Multistate Milking Match-up，MMM），他们已经摸清了其他队的实力。他们的总产奶量只要大于等于 $X$ 加仑（$1 \leq X \leq 10^6$），就能赢得胜利。

每头奶牛都能为全队贡献一定量的牛奶，数值在 $-10^4$ 到 $10^4$ 加仑之间（为啥有负数？因为有些奶牛会打翻其他奶牛产的牛奶）。

MMM 的目标是通过合作，增进家庭成员间的默契。为了支持比赛精神，奶牛们希望在赢得比赛的前提下，有尽可能多对奶牛间存在直系血缘关系。当然，所有奶牛都是女性，因此这里的直系血缘关系就是母女关系。

现在 FJ 摸清了所有奶牛间的血缘关系，希望算出一个团队在赢得胜利的前提下，最多有多少对奶牛存在血缘关系。注意：如果一个团队由某头奶牛和她的母亲和外祖母组成的话，这个团队只有两对血缘关系（她和她的母亲，她的母亲和外祖母）。

【输入格式】

第一行两个整数 $N,X$。

接下来 $N$ 行，每行两个整数，第一个整数是它能为团队贡献的产奶量，第二个整数为它的母亲的编号，如果她的母亲不在牛群里，这个数字为 $0$。

保证血缘关系不会出现环。

【输出格式】

输出在获胜的前提下，一个团队中最多存在多少血缘关系。

特别地，如果不存在一个团队能获胜，输出 $-1$。


【样例输入】

5 8
-1 0
3 1
5 1
-3 3
2 0

【样例输出】

2

【提示】

最优的队伍包含 $1,2,3,5$ 这四头奶牛，总产奶量为 $9$ 加仑，共有两对血缘关系（$1,2$ 和 $1,3$）。

虽然 $2,3,5$ 这个组合产奶量更大，但是这个组合里没有血缘关系。

Hint

by hansang:

#include<bits/stdc++.h>
using namespace std;
const int N=510;
int f[N][N][2], n, a[N];
vector<int> G[N]; 
void dfs(int x){
	f[x][0][0]=0;
	f[x][0][1]=a[x];
	for(int y: G[x]){
		dfs(y);
		for(int i=n; i>=0; i--){
			for(int j=i; j>=0; j--){
				f[x][i][0]=max(f[x][i][0], f[x][j][0]+max(f[y][i-j][1], f[y][i-j][0]));
				if(i-j>=1) f[x][i][1]=max(f[x][i][1], f[x][j][1]+f[y][i-j-1][1]);
				f[x][i][1]=max(f[x][i][1], f[x][j][1]+f[y][i-j][0]);
			}
		}
	}
}
void work(){
	int m; scanf("%d%d", &n, &m);
	for(int i=1; i<=n; i++){
		int x=i, y; scanf("%d%d", &a[i], &y);
		G[y].push_back(x);
	} 
	memset(f, -0x3f, sizeof(f));
	a[0]=0; dfs(0);
	for(int i=n; i>=0; i--){ 
		if(f[0][i][0]<m) continue;
		printf("%d\n", i);
		return ;
	}
	printf("-1\n");
}
int main(){
	work();
	return 0;
}