First of all, we can't retrieve the data of the tree if a path value for a vertex is less than a path value for any of its ancestors, because Milad calculated all the path values from the root 1. So, a path value for a vertex can't be less than a path value for any of its ancestors.

Now, in order to keep the summation of the values of all vertices minimum, we try to add values to the lost path values for vertices of higher-level of the tree (close to the root) if possible so that the added values can contribute to the maximum number of path values. In order to do that, we can do a depth-first search traversal to replace a lost path value by the minimum path value of its subtree (ignoring -1 as the minimum).

Some path values may remain lost. Now, we do another depth-first search traversal to replace the remaining lost path values by the path value (not lost) of its first ancestor, as for these path values, ai can be 0. We can easily say that if all sumi is -1, then these all can be replaced by 0.

Now, we can get all ai by subtracting sumparenti from sumi and get the summation of all ai. a1 is always sum1.

85%
Solution Ratio

tmwilliamlin168Earliest,

MD.ROKONMIAFastest, 0.1s

dragoonLightest, 6.9 MB

MD.ROKONMIAShortest, 931B

Toph uses cookies. By continuing you agree to our Cookie Policy.