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

The complexity can be demonstrated with the following problem:

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 NameDifficultyTags
Show TagsDP
Show TagsNT

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!