Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
The task states that Bobi has the power to turn on or off the superpower of each super pipe. Notice that it is always better to turn on the superpower of a pipe if the current amount of liquid flowing through it is larger than or equal to 
~1~, because that way we increase the total amount of liquid in the tree. In the case when the current amount of liquid in the pipe is smaller than ~1~, we will not use the superpower because that would decrease the total amount of liquid in the tree.
How will we find the minimal 
~L~ that meets the conditions from the task (that each ant gets at least 
~K_i~ liters of liquid)?
Let's fixate a concrete ~L~ and calculate how much liquid each leaf (ant) gets with that flow. We can calculate this by simply traversing the tree and literally simulating the pipe system from the task. Let's assume that for this ~L~ all ants got a sufficient amount of liquid. This means that for an even bigger value ~L~ all ants will get a sufficient amount of liquid so we only need to check what are the smaller values of ~L~ that satisfy the "ant" conditions.
This conclusion leads us to the binary search algorithm with which we can calculate the smallest required ~L~.
The experienced eye won't miss that the described algorithm doesn't actually work. More precisely, it doesn't work when implemented on a computer. Imagine this situation: given a chain in a tree we initially have a lot of squaring and then we have a lot of pipes that get only 
~1\%~ of liquid from the parent node. Firstly, the amount of liquid becomes very large (a lot larger than 
~2 \times 10^9~ - the upper solution bound), and then the ~1\%~ pipes decrease it so it fits below the upper bound, but that number is not precise because, even though the double data type stores large numbers, it doesn't keep absolute precision. This problem can be solved if we logarithmize all numbers so the operations of squaring and multiplying become operations of summation (and thus relative precision is kept).
Since advanced handling of floating point data types doesn't belong to high school competition required knowledge, this solution wasn't expected. Therefore, there were no test data in which the described situation appears.
We leave finding the algorithm in linear complexity for the readers to practise.
Comments