Input File: sculpin.txt
Output File: sculpout.txt
Time Limit: 1 second
As a highly acclaimed sculpture artist, you have been commissioned to make an abstract 3-dimensional artwork to commemorate the Melbourne International Fruit Festival.
You have decided to construct an elaborate tree by joining apples together with sticks of wood. The artwork will have a single apple at its base, with two wooden sticks rising up to meet new apples. Each of these apples has two more wooden sticks rising up to meet two new apples, and so on. An example of such a tree is illustrated below, where the apples are numbered from 1 to 9 and the lengths of the sticks are shown.
Note that some apples have two new sticks rising up, and others have none. You never have only one stick rising up, since this upsets the delicate artistic balance of the work.
Consider the apples with no new sticks rising up — call these the top apples. In the example above, the top apples are numbers 4, 5, 7, 8 and 9. By examining the stick lengths, we can measure the distance from each top apple to the base of the tree. These distances are as follows.
The Director of the festival has passed by to inspect your artwork. She likes the idea, but is unhappy that the top apples look so messy. You are therefore instructed to lengthen some of the wooden sticks so that all the top apples are precisely the same distance from the base.
Unfortunately you are running short of wood, and so you would like to add the smallest total length possible. For the example above, you could change the stick lengths as follows (changed lengths are indicated with arrows).
Here you have increased the sticks by a total length of 1+3+2 = 6 (which is the smallest total increase possible). The distances from the top apples to the base are now as follows.
Since these distances are all the same, the Director is happy and you can exhibit your artwork to receive the fame and glory that such a piece deserves.
You must write a program that reads in a tree of apples and sticks, and then determines the smallest total increase in stick lengths that is needed to bring all top apples to the same distance from the base.
The first line of input will consist of a single integer n representing the number of apples (1 <= n <= 50,000). These apples will be numbered 1,2,...,n. Following this will be n additional lines, describing apples 1,2,...,n in order.
Consider the line describing apple number i. If this is a top apple, the line will consist of four zeroes. Otherwise, the line will consist of the four integers a, x, b and y (each separated by a single space). This signifies that there is one stick of length x rising to meet apple number a, and another stick of length y rising to meet apple number b. You are guaranteed that i < a,b <= n and that 1 <= x,y <= 1000.
Note that, except for the base apple, each apple has precisely one stick that meets it from underneath. The base apple is always apple number 1.
Your output must consist of a single line containing a single integer, which is the smallest total increase in stick lengths that is required. You are guaranteed that this answer will never be more than 2,000,000,000.
The following input file describes the example from earlier.
9 2 3 3 4 4 1 5 2 6 3 7 2 0 0 0 0 0 0 0 0 8 1 9 1 0 0 0 0 0 0 0 0 0 0 0 0
The score for each input file will be 100% if the correct answer is written to the output file and 0% otherwise.