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 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]}.

#include <iostream>
#include <vector>
using namespace std;
constexpr int MAX_GOODS = 5000;
constexpr long long INF = 1e18;
int initial[MAX_GOODS + 1];
int discounted[MAX_GOODS + 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, Tree
Show TagsDP, Tree
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!