Problem E
Juice
In the Favela of Rio de Janeiro there was a flicker of light. After months of careful building, they finally connected the generator to the thousands of extension cords and the slum was illuminated by millions of bright lights
However, the capacity of the extension cords was not enough to meet the energy demands of all the houses in the slum. Thus, the engineers had to carefully select which houses should be powered, and which should not, prior to connecting the power generator. Their idea was to power as many houses as possible, based on the energy demands of each house, and the capacities of the extension cords.
More specifically, the generator and all the houses are represented by nodes, and extension cords are represented by directed edges between them. Furthermore, every house node $i$ gets power from exactly one other node $p_ i$ and has a non-negative power demand $r_ i$. You can assume that each house can get power from the generator either directly or via other houses.
The flow through an extension cord $(p_ i, i)$ is the sum of the energy demands that are met in the subtree rooted at $i$, and this flow can not exceed the capacity $c_ i$ of the extension cord. A node which does not have its energy demand satisfied can still have some of its children satisfied. The generator produces an amount of energy that surpasses by far the total capacity of the extension cords connected to it, so can be treated as an infinite energy source.
Given the same data as the engineers, find out how many houses the engineers were able to cover the energy demands of.
Input
The first line of the input contains a single integer $0 \leq N \leq 1\, 000$, the number of houses in the slum. $N$ lines follow in the format $p_ i\ r_ i\ c_ i$, where $0 \leq p_ i \leq N$ is the parent node of house $i$, $0 \leq r_ i \leq 100$ is the energy demand of house $i$ and $1 \leq c_ i \leq 100$ is the capacity of the extension cord connecting house $i$ to house $p_ i$. The power generator has index $0$.
Output
Output the maximum number of power requirements that can be met.
| Sample Input 1 | Sample Output 1 |
|---|---|
3 0 3 2 0 100 100 1 1 1 |
2 |
