DP on Trees - Combining Subtrees
Author: Benjamin Qi
Focus Problem – try your best to solve this problem before continuing!
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 !
Time Complexity of Merging Subtrees
The complexity can be demonstrated with the following problem:
You have an list of ones and a counter initially set to . While the list has greater than one element, remove any two elements and from the list, add to the counter, and add to the list. In terms of , what is the maximum possible value of the counter at the end of this process?
Show TagsDP, Tree
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!