DP on Trees - Combining Subtrees
Author: Benjamin Qi
This was the first problem I saw that involved this trick.
For two vectors and , define the vector to have entries for each .
Similar to the editorial, define to be the minimum cost to buy exactly goods out of the subtree of if we don't use the coupon for , and define to be the minimum cost to buy exactly goods out of the subtree of if we are allowed to use the coupon for . We update with one of the child subtrees of by setting , and similarly for .
The editorial naively computes a bound of on the running time of this solution. However, this actually runs in !