Karen and Supermarket
Contest: Codeforces Round 419 (Div. 1)
Difficulty rating: 2400
Tags: brute force, dp, trees

On the way home, Karen decided to stop by the supermarket to buy some groceries.

She needs to buy a lot of goods, but since she is a student her budget is still quite limited. In fact, she can only spend up to b dollars.

The supermarket sells n goods. The i-th good can be bought for ci dollars. Of course, each good can only be bought once.

Lately, the supermarket has been trying to increase its business. Karen, being a loyal customer, was given n coupons. If Karen purchases the i-th good, she can use the i-th coupon to decrease its price by di. Of course, a coupon cannot be used without buying the corresponding good.

There is, however, a constraint with the coupons. For all i ≥ 2, in order to use the i-th coupon, Karen must also use the xi-th coupon (which may mean using even more coupons to satisfy the requirement for that coupon).

Karen wants to know the following. What is the maximum number of goods she can buy, without exceeding her budget b?

Input format:
The first line of input contains two integers n and b (1 ≤ n ≤ 5000, 1 ≤ b ≤ 109), the number of goods in the store and the amount of money Karen has, respectively.

The next n lines describe the items. Specifically:

- The i-th line among these starts with two integers, ci and di (1 ≤ di < ci ≤ 109), the price of the i-th good and the discount when using the coupon for the i-th good, respectively.
- If i ≥ 2, this is followed by another integer, xi (1 ≤ xi < i), denoting that the xi-th coupon must also be used before this coupon can be used.

Output format:
Output a single integer on a line by itself, the number of different goods Karen can buy, without exceeding her budget.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case, Karen can purchase the following 4 items:

- Use the first coupon to buy the first item for 10 - 9 = 1 dollar.
- Use the third coupon to buy the third item for 12 - 2 = 10 dollars.
- Use the fourth coupon to buy the fourth item for 20 - 18 = 2 dollars.
- Buy the sixth item for 2 dollars.

The total cost of these goods is 15, which falls within her budget. Note, for example, that she cannot use the coupon on the sixth item, because then she should have also used the fifth coupon to buy the fifth item, which she did not do here.

In the second test case, Karen has enough money to use all the coupons and purchase everything.

Example input:
6 16
10 9
10 5 1
12 2 1
20 18 3
10 2 3
2 1 5

Example output:
4

Example input:
5 10
3 1
3 1 1
3 1 2
3 1 3
3 1 4

Example output:
5

Editorial:
Instead of asking for the maximum number of items we can buy with b dollars, let's ask instead for the minimum cost to buy j items for all j. Afterwards, we can simply brute force all j to find the largest j that still fits within her budget b.
Note this problem is actually on a rooted tree, with root at node 1; the constraint xi < i guarantees there are no cycles in this problem. The coupon requirement essentially means that if we buy good i at the discounted price, we also need to buy good xi at the discounted price, and so on. If we don't buy at discounted price there are no constraints (except that Karen can afford it. Unfortunately, she isn't a criminal.)
There is a rather straightforward O(n3) dynamic programming solution to this problem, as follows:
Let fi, j be the minimum cost to buy j items in the subtree of i if we can still use coupons, and gi, j the minimum cost to buy j items in the subtree of i if we cannot use any more coupons.
We know that for all leaves, fi, j = ci - di and gi, j = ci.
We can compute gi, j for all nodes as well; this is simply the sum of the j smallest c's in the subtree of i. This can be done straightforwardly in O(n2) or $$O(n^2 \log n)$$.
To compute this fi, j for some non-leaf node i, we should initialize fi, 1 = ci - di.
Now, we can add each of the children of i one by one, and try each j. Suppose we take k elements from one of the children. Then we have fi, j = min(fi, j, fi, j - k + fi, k). We just have to make sure to implement it in a way that we don't inadvertently take elements multiple times, usually by making an auxiliary array.
Finally, we set fi, j = min(fi, j, gi, j) to consider not using the coupons. Note that we can't do this at the start, because otherwise it could cause conflicts.
This runs in O(n3), which is too slow. This is because there are n nodes, and to compute fi, j for all j in that node, it takes $${\cal O}(n\sum_{h\in p_i}s(h))$$ where pi is the set of all of the children of i, and s(h) is the subtree size of node h. This sum turns out to be O(n2), and so the final runtime is O(n3).
How could we make it faster? Take the largest (in terms of nodes) child of subtree i. Can we avoid iterating through this?
Yes, we can! Suppose our tree was binary. Now, we can compute fi, j = min0 ≤ k < j(fa, j - k - 1 + fb, k + ci - di), where a and b are the subtrees of i, with s(a) ≥ s(b). This skips iterating through the larger subtree a.
We can extend this to non-binary trees, too; just do this to skip the largest subtree, and then add the rest like before.
The runtime of the transition is now $$O \left( n \left( \sum_{h \in p_i} s(h) - s(a) \right) \right)$$, which turns out to be just O(n). The final runtime is hence O(n2) (or $$O(n^2 \log n)$$, depending on the algorithm used for the greedy portion.) This is sufficient to solve this problem.