Rare
0/6

# DP on Trees - Combining Subtrees

Author: Benjamin Qi

?

### Prerequisites

SolutionTime Complexity of Merging SubtreesProblems

Focus Problem – read through this problem before continuing!

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

## Solution

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

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

Code

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

## Time Complexity of Merging Subtrees

The complexity can be demonstrated with the following problem:

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

Solution

## Problems

StatusSourceProblem NameDifficultyTags
COCINormal
CFNormal
IOINormal
CFNormal
Show TagsDP
DMOJHard
Show TagsNT

### 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!