[Usaco2006 Mar] Milk Team Select 产奶比赛

题目描述

Farmer John's N (1 <= N <= 500) cows are trying to select the milking team for the world-famous Multistate Milking Match-up (MMM) competition. As you probably know, any team that produces at least X (1 <= X <= 1,000,000) gallons of milk is a winner. Each cow has the potential of contributing between -10,000 and 10,000 gallons of milk. (Sadly, some cows have a tendency to knock over jugs containing milk produced by other cows.) The MMM prides itself on promoting family values. FJ's cows have no doubt that they can produce X gallons of milk and win the contest, but to support the contest's spirit, they want to send a team with as many parent-child relationships as possible (while still producing at least X gallons of milk). Not surprisingly, all the cows on FJ's farm are female. Given the family tree of FJ's cows and the amount of milk that each would contribute, compute the maximum number of parent-child relationships that can exist in a winning team. Note that a set of cows with a grandmother-mother-daughter combination has two parent-child relationships (grandmother-mother, mother-daughter).

    约翰的N(1≤N≤500)头奶牛打算组队去参加一个世界级的产奶比赛(Multistate Milking

Match-up，缩写为MMM)．她们很清楚其他队的实力，也就是说，她们派出的队只要能产出至少X(I≤X≤1000000)加仑牛奶，就能赢得这场比赛．    每头牛都能为集体贡献一定量的牛奶，数值在-10000到10000之间（有些奶牛总是想弄翻装着其他奶牛产的奶的瓶子）．

    MMM的举办目的之一，是通过竞赛中的合作来增进家庭成员之间的默契．奶牛们认为她们总是能赢得这场比赛，但为了表示对比赛精神的支持，她们希望在选出的队伍里能有尽可能多的牛来自同一个家庭，也就是说，有尽可能多对的牛有直系血缘关系（当然，这支队伍必须能产出至少X加仑牛奶）．当然了，所有的奶牛都是女性，所以队伍里所有直系血亲都是母女关系．    约翰熟知所有奶牛之间的血缘关系．现在他想知道，如果在保证一支队伍能赢得比赛的情况下，队伍中最多能存在多少对血缘关系．注意，如果一支队伍由某头奶牛和她的母亲、她的外祖母组成，那这支队伍里一共有2对血缘关系（这头奶牛外祖母与她的母亲，以及她与她的母亲）．

---

输入格式

* Line 1: Two space-separated integers, N and X. * Lines 2..N+1: Line i+1 contains two space-separated integers describing cow i. The first integer is the number of gallons of milk cow i would contribute. The second integer (range 1..N) is the index of the cow's mother. If the cow's mother is unknown, the second number is 0. The family information has no cycles: no cow is her own mother, grandmother, etc. 

---

输出格式

* Line 1: The maximum number of parent-child relationships possible on a winning team. Print -1 if no team can win.

    输出在一个能获胜的队伍中，最多可能存在的有血缘关系的牛的对数．如果任何一支队伍都不可能获胜，输出-1.

---

样例输入

5 8
-1 0   //第一个数字代表这头奶的产量,第二个数字代表其父亲点是哪一个.
3 1
5 1
-3 3
2 0

INPUT DETAILS:

There are 5 cows. Cow 1 can produce -1 gallons and has two daughters, cow
2 and 3, who can produce 3 and 5 gallons, respectively. Cow 3 has a
daughter (cow 4) who can produce -3 gallons. Then there's cow 5, who can
produce 2 gallons.

---

样例输出

2

---

提示

 

---

题目来源

Gold