# DP on Trees - Combining Subtrees

Author: Benjamin Qi

### Prerequisites

?

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

CF | Normal | Check CF |

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)$.

Similar to the editorial, define $\texttt{dp[x][0][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][1][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][0]}$ with one of the child subtrees $t$ of $x$ by setting $\texttt{dp[x][0]}=\texttt{dp[x][0]}\oplus \texttt{dp[t][0]}$, and similarly for $\texttt{dp[x][1]}$.

Code

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

## Time Complexity of Merging Subtrees

### This section is not complete.

add proof

## Problems

Status | Source | Problem Name | Difficulty | Tags | Solution |
---|---|---|---|---|---|

COCI | Normal | ||||

CF | Normal | Check CF | |||

DMOJ | Normal | ||||

CF | Normal | ## Show TagsDP | |||

DMOJ | Hard | ## Show TagsNT |