Broken Tree
Contest: Codeforces Round 392 (Div. 2)
Difficulty rating: 2600
Tags: dfs and similar, dp, graphs, greedy, trees

You are given a tree that has n vertices, which are numbered from 1 to n, where the vertex number one is the root. Each edge has weight wi and strength pi.

Botanist Innokentiy, who is the only member of the jury of the Olympiad in Informatics, doesn't like broken trees.

The tree is broken if there is such an edge the strength of which is less than the sum of weight of subtree's edges to which it leads.

It is allowed to reduce weight of any edge by arbitrary integer value, but then the strength of its edge is reduced by the same value. It means if the weight of the edge is 10, and the strength is 12, then by the reducing the weight by 7 its weight will equal 3, and the strength will equal 5.

It is not allowed to increase the weight of the edge.

Your task is to get the tree, which is not broken, by reducing the weight of edges of the given tree, and also all edged should have the positive weight, moreover, the total weight of all edges should be as large as possible.

It is obvious that the strength of edges can not be negative, however it can equal zero if the weight of the subtree equals zero.

Input format:
The first line contains the integer n (1 ≤ n ≤ 2·105) — the number of vertices in the tree. The next n - 1 lines contains the description of edges. Each line contains four integers x, y, w, p (1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109), where x and y — vertices which connect the edge (the vertex number x is the parent of the vertex number y), w and p are the weight and the strength of the edge, accordingly. It is guaranteed that the edges describe the tree with the root in the vertex 1.

Output format:
If it is impossible to get unbroken tree from the given tree, print -1 in the only line.

Otherwise, the output data should contain n lines:

In the first line print the number n — the number of vertices on the tree.

In the next n - 1 lines print the description of edges of the resulting tree. Each line should contain four integers x, y, w, p (1 ≤ x, y ≤ n, 1 ≤ w ≤ 109, 0 ≤ p ≤ 109), where x and y — vertices, which the edge connects (the vertex number x is the parent of the vertex number y), w and p are the new weight and the strength of the edge, accordingly.

Print edges in the same order as they are given in input data: the first two integers of each line should not be changed.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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

Example output:
3
1 3 5 7
3 2 4 3

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

Example output:
-1

Editorial:
First, let's calculate min and max weight for subtrees of each vertex.
Minimal weight of a subtree is sum of minimal weights of all adjacent to the root of current subtree subtrees and sum of weights of all outgoing edges reduced in weight to minimal possible.
Thus, minimal weight is $$dpmi n_{x} = \sum_{i=1}^{n_{x}} dpmi n_{y_{x}, i} + w_{x,i} - min(p_{x,i}-dpmi n_{y_{x},i},w_{x,i}-1)$$, where x —subtree root, nx —number of outgoing edges from x, yx, i — each adjacent to x vertex, px, i — its strength, wx, i — its weight.
Note that minimal weight should be less or equal to strength of incoming edge. If this condition isn't satisfied for at least one subtree then the answer is  - 1.
Maximal weight of a subtree is sum of maximal weights of all adjacent to the root of current subtree subtrees and sum of weights of all outgoing edges. Note that this maximum should stay in such boundaries that the tree remains unbroken. So maximal weight should not exceed strength of incoming edge of a root.
Therefore, maximum is $$$$, where x —subtree root, pz, i — weight of an incoming edge of x, that is j-th edge outgoing from some vertex z, nx —number of outgoing edges from x, yx, i — each adjacent to x vertex, wx, i — its weight.
After that, let's calculate current weight of every subtree to find difference between actual value and the optimal one. Weight of subtree is sum of weights of all adjacent to the root of current subtree subtrees and sum of weights of all outgoing edges.
Then actual weight is $$dpW_{x} = \sum_{i=1}^{n_{x}} dpW_{y_{x,i}} + w_{x,i}$$, where x —subtree root, nx —number of outgoing edges from x, yx, i — each adjacent to x vertex, wx, i — its weight.
One dfs from the root of the tree is enough to calculate all these values.
Note that dpmin, dpmax and dpW are set to 0 for leaves .
dpmaxx is maximal possible weight of each subtree, so weight of the whole tree can be reduced to dpmax1, it means that weight of subtree of vertex 1 should be reduced by dpW1 - dpmax1.
Next goal is to learn how to reduce weight of subtree of vertex x by s units. At first, you should reduce weights of subtrees of adjacent to x vertices to their maximum. So after this step $$s = s - \sum_{i=1}^{n_x} dpW_{y_x,i} - dpmax_{y_x,i}$$. Then while s > 0, reduce weight of each next subtree. If it's still s > 0 then reduce weights of outgoing edges from x maintaining unbroken state of tree.
This process also takes one dfs.
Overall complexity is the complexity of two dfs calls, that is O(n).