Problem C
Dams in Distress
Freyr, being the god of rain, knows exactly how much water is needed to wash the war camp away, and for each dam knows its exact capacity and how much water is currently stored there. Freyr, also being the god of prosperity and harvest, has better things to do than making it rain everywhere all day, so Freyr decides to only make it rain at a single place (either a dam, or the war camp), and to make it rain as little as possible in that place. What is the minimum amount of rain that Freyr needs to make to wash away the giants war camp, provided he carefully chooses the best location for the rain?
The network of dams and the war camp form a rooted tree, where the war camp is the root and the parent of a dam is the location (either another dam, or the war camp) immediately downstream of the dam. See Figure 1 for an example.
Input
The first line of input consists of two integers $n$ and $w$ ($1 \le n \le 2 \cdot 10^5$, $1 \le w \le 10^9$), the number of dams and the amount of water needed to wash away the war camp, respectively. Then follow $n$ lines, describing the $n$ dams. The dams are numbered from $1$ to $n$.
The $i$th line contains three integers $d_ i$, $c_ i$ and $u_ i$ ($0 \le d_ i < i$, $1 \le c_ i \le 10^9$, $0 \le u_ i < c_ i$), where $d_ i$ is the number of the dam immediately downstream of dam $i$ (or $0$ if the war camp is immediately downstream of dam $i$), $c_ i$ is the maximum capacity of dam $i$, and $u_ i$ is the current amount of water in dam $i$.
Output
Output the minimum amount of rain Freyr needs to make at one location, which will result in at least $w$ water reaching the war camp.
Sample Input 1 | Sample Output 1 |
---|---|
4 75 0 100 50 1 49 10 1 50 0 3 50 48 |
2 |
Sample Input 2 | Sample Output 2 |
---|---|
4 13 0 12 1 1 6 1 2 4 1 3 10 0 |
10 |
Sample Input 3 | Sample Output 3 |
---|---|
4 1 0 100 50 1 49 10 1 50 0 3 50 48 |
1 |