As you can check here, it was very hard for many people (including me) to understand editorial's solution for problem 758E - Broken Tree. The solution has two parts: one DFS to compute the current, minimum and maximum weights for each subtree and check if we should print -1; and then a second DFS to reduce the values of the edges and fix the tree. The explanation for the first part is great, just check it and remember to ignore the "dp" prefix in variable names (there is no overlapping subproblems, so that's not dynamic programming). But when it came to explain the second part (which is the harder one), the author decided to spare words. So here it goes the full explanation. I'll assume you've read the explanation for the first part and I'll use the same (bad) variable names.

Before calling dfs2(1), we should create an array goal such that goal[u] will store how many units we should remove from the edges of the subtree rooted at u. Therefore we should start with goal[1] = dpw[1]-dpmax[1].

The second DFS is a "pre-order" traversal in the following sense. Suppose we're visiting u. First, we should break the value goal[u] and store the pieces in goal[v] for each edge (u, v). In other words, we should break the goal for vertex u into possibly smaller goals for the children of u. Then we should call dfs2(v) recursively only after no more transfers are possible from goal[u] to the branch that contains v. Let's see some code for this idea.

First, let's code a helper function to transfer w units from goal[u] to goal[v]:

transfer(u, v, w):
  goal[u] -= w
  goal[v] += w

The first reduction is to remove the obligatory units, i.e., dpw[v]-dpmax[v]:

dfs2(u):
  for each (u, v, w, p) in E:
    transfer(u, v, dpw[v]-dpmax[v])

After this reduction, it's possible that goal[u] is still greater than zero (but never less than zero, by the construction of the arrays dpw and dpmax). Then we should greedily remove some units from the subtrees rooted at the children of u, assuming their current weights as dpmax[v]:

  for each (u, v, w, p) in E:
    transfer(u, v, min(goal[u], dpmax[v]-dpmin[v]))

We do that because it's always better to remove units from deeper edges (this is not hard to see). It's important to note that these two loops cannot be merged. We should take some additional units from the subtrees rooted at the children of u only if taking the obligatory units was not enough.

Now, if goal[u] is still greater than zero, then all we can do is to take some units from the edges adjacent to u, assuming the current weights of the subtrees as dpmin[v]. This is the last transfer operation from u to each of its children, so we can finally do the recursion:

  for each (u, v, w, p) in E:
    tmp = min(goal[u], min(w-1, p-dpmin[v]))
    w -= tmp
    p -= tmp
    goal[u] -= tmp
    dfs2(v)

I'd like to thank Jakube for his submission 24488076 which helped me to understand the editorial's solution and hope this post can help others.

Here is my code: 24557663