DP on Trees - Combining Subtrees

Author: Benjamin Qi


Focus Problem – read through this problem before continuing!

This was the first problem I saw that involved this trick.


For two vectors aa and bb, define the vector c=abc=a\oplus b to have entries ci=mink=0i(ak+bik)c_i=\min_{k=0}^i\left(a_k+b_{i-k}\right) for each 0i<size(a)+size(b)10\le i < \text{size}(a)+\text{size}(b)-1.

Similar to the editorial, define dp[x][0][g]\texttt{dp[x][0][g]} to be the minimum cost to buy exactly gg goods out of the subtree of xx if we don't use the coupon for xx, and define dp[x][1][g]\texttt{dp[x][1][g]} to be the minimum cost to buy exactly gg goods out of the subtree of xx if we are allowed to use the coupon for xx. We update dp[x][0]\texttt{dp[x][0]} with one of the child subtrees tt of xx by setting dp[x][0]=dp[x][0]dp[t][0]\texttt{dp[x][0]}=\texttt{dp[x][0]}\oplus \texttt{dp[t][0]}, and similarly for dp[x][1]\texttt{dp[x][1]}.


The editorial naively computes a bound of O(N3)\mathcal{O}(N^3) on the running time of this solution. However, this actually runs in O(N2)\mathcal{O}(N^2)!

Time Complexity of Merging Subtrees

Try to do the following (easy) problem first:

You have an list of NN ones and a counter initially set to 00. While the list has greater than one element, remove any two elements aa and bb from the list, add aba\cdot b to the counter, and add a+ba+b to the list. In terms of NN, what is the maximum possible value of the counter at the end of this process?



StatusSourceProblem NameDifficultyTagsSolutionURL
CFNormalCheck CF
Show Tags


Show Tags


Module Progress:

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!

Give Us Feedback on DP on Trees - Combining Subtrees!

Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.