This blog is for documenting my learning journey in competitive programming. I hope someone enjoys it and finds it helpful for their own learning.
Credit to the USACO Guide and ChatGPT for introducing me to many great memory-reduction methods and fun problems.
Before Starting
- Before learning DP on trees, I would recommend trying other types of DP, such as knapsack, basic DP, bitmask DP, and digit DP.
- If you already know these types of DP, understanding tree DP will be MUCH, MUCH easier.
Theory
- Tree DP mainly focuses on minimization, maximization, and grouping, although counting is also quite common.
- The idea is to find the optimal
dp[node][state]for a subtree and transition from the children's subtrees to the parent's subtree, with leaves serving as base cases. - This works because the DP flows in ONE DIRECTION, which is why tree DP can technically also be applied to a DAG.
- There is no universal template for tree DP, but it will often look something like this:
void dfs(int node, int parent) {
for (auto &p : adj[node]) {
if (p != parent) {
dfs(p, node);
// Transition DP.
}
}
// More transitions.
}
Problems
1. Codeforces 1387B1
This problem can be solved greedily, but if you cannot find the greedy solution, here is my much longer DP solution :))
DP solution
How can we minimize the total movement? My first instinct was to swap a node with its neighbor, achieving the minimum distance. Let's call this a pair swap.
However, we cannot use only pair swaps for shapes like stars, where one node might be a neighbor of a quadrillion other nodes. So, the second shape to consider is a star.
Why a star? If a branch of the star has a length greater than 2, we can perform a pair swap and shrink it.
Now, we just need to calculate the cost of a star with
Unable to parse markup [type=CF_MATHJAX]
$ children:
- The first child contributes
Unable to parse markup [type=CF_MATHJAX]
$. - Each additional child adds another
Unable to parse markup [type=CF_MATHJAX]
$.
This works because the first child can move to the center, the center can move to another child, and the remaining children can swap among themselves, each moving a distance of
Unable to parse markup [type=CF_MATHJAX]
$.
We can formulate the DP using these states:
dp[i][0]: Node
Unable to parse markup [type=CF_MATHJAX]
$ is not part of any star. - dp[i][1]: Node
Unable to parse markup [type=CF_MATHJAX]
$ is a child of a star. - dp[i][2]: Node
Unable to parse markup [type=CF_MATHJAX]
$ is the center of a star.
Then trace the answer back :) Doing DP for this problem was very painful, which I learned firsthand.
Greedy solution
The greedy solution is to swap each node with its parent if either the node or its parent is still in its original home. Each swap adds
Unable to parse markup [type=CF_MATHJAX]
$ to the answer.
Why does this work?
Using the pair-swap idea, we are left with stars. Swapping a node with its parent can have the following results:
- Both nodes leave their original homes, which is clearly optimal.
- One node leaves its original home.
This idea helps us minimize the number of swaps of the second type, allowing us to achieve the minimum cost.
2. Codeforces 1521D
This problem is simpler than the previous one because we can use the following tree DP approach:
dp[i][0]: Keep
Unable to parse markup [type=CF_MATHJAX]
$ edges. - dp[i][1]: Keep
Unable to parse markup [type=CF_MATHJAX]
$ edge. - dp[i][2]: Keep
Unable to parse markup [type=CF_MATHJAX]
$ edges.
We can formulate the transitions as follows:
dp[i][0]: Sumdp[child][2]over all children.dp[i][1]: Sort the children bydp[child][2] - dp[child][1]to find the greatest improvement, then takechildren[0].dp[i][2]: Use the same idea asdp[i][1], but take two children.
After that, trace the answer back using DSU.
3. AtCoder ABC259 F
For me, intuition just popped up and said, "Use dp[i][2]."
dp[i][0]: Connect to
Unable to parse markup [type=CF_MATHJAX]
$ edges leading to children. - dp[i][1]: Connect to
Unable to parse markup [type=CF_MATHJAX]
$ edges leading to children.
The sorting idea is the same as in the previous problem.
4. USACO — cpid=1019
The idea is to simulate the paths. Why? For a fixed
Unable to parse markup [type=CF_MATHJAX]
$, the length of the path coming out of a subtree is fixed, so we just need to simulate this and use a map to pair paths.
The second observation is that if we can partition the edges into paths of length
Unable to parse markup [type=CF_MATHJAX]
$, then
Unable to parse markup [type=CF_MATHJAX]
$ must be a factor of
Unable to parse markup [type=CF_MATHJAX]
$. Therefore, we only need to traverse each
Unable to parse markup [type=CF_MATHJAX]
$ where k % i == 0.
5. USACO — cpid=1497
Since this is about tree DP, let's think: this problem asks us to minimize something. If the graph were a tree, could we use DP on it?
Build a graph with an edge from
Unable to parse markup [type=CF_MATHJAX]
$ to
Unable to parse markup [type=CF_MATHJAX]
$. If we perform an operation on node
Unable to parse markup [type=CF_MATHJAX]
$, we can consider the following cases:
- Connect it to some other node
Unable to parse markup [type=CF_MATHJAX]
$. That node must connect to itself, costing
Unable to parse markup [type=CF_MATHJAX]
$. This is not optimal because we could simply connect node
Unable to parse markup [type=CF_MATHJAX]
$ to itself for
Unable to parse markup [type=CF_MATHJAX]
$. - Connect node
Unable to parse markup [type=CF_MATHJAX]
$ to itself, costing
Unable to parse markup [type=CF_MATHJAX]
$. - Perform an operation on
Unable to parse markup [type=CF_MATHJAX]
$ to connect it to itself, costing
Unable to parse markup [type=CF_MATHJAX]
$.
In the end, there are only two operations to consider: performing an operation on
Unable to parse markup [type=CF_MATHJAX]
$ or on
Unable to parse markup [type=CF_MATHJAX]
$.
We can formulate the tree DP as follows:
dp[i][0]: No operation. Add the minimumdp[child][1] + min(dp[child][0], dp[child][1]).dp[i][1]: Perform an operation.C[i] + min(dp[child][0], dp[child][1]).
Now, back to the actual problem. The graph is a functional graph, meaning that it contains cycles with trees attached to their nodes. Therefore, we MUST break the cycle to use tree DP.
We can do this by considering the state of the last node in the cycle:
- No operation on the last node: It cannot support the first node in the cycle, turning the cycle into a tree. Perform tree DP on it.
- Perform an operation on the last node: Take the minimum of performing or not performing an operation on the first node. Then break both the last and first nodes out of the cycle, creating two separate trees and allowing us to perform tree DP on both.
6. Szkopuł Problem
This is a functional graph, so we can use the Bessie Function idea to perform DP on it.
BUT THERE'S A CATCH: 32 MB OF MEMORY.
So that's sad. Let's do some memory calculations:
F[i]andvisited[i]:
Unable to parse markup [type=CF_MATHJAX]
$ MB. - dp[i][2] and cost[i][2]:
Unable to parse markup [type=CF_MATHJAX]
$ MB. - vector<vector<ll>> adj: Absolutely over the limit.
We can optimize the adjacency list using a condensed edge array, keeping Start and Arr for
Unable to parse markup [type=CF_MATHJAX]
$ MB. For each node, we store the range
Unable to parse markup [type=CF_MATHJAX]
$ containing its edges in Arr.
Then, we need to replace recursion with a more memory-efficient approach. We can use indegree peeling, continuously processing nodes with indegree
Unable to parse markup [type=CF_MATHJAX]
$. This allows us to process the graph from the leaves upward.
After peeling off the trees, only the cycles remain. Then, we can use the Bessie Function idea and perform DP on each cycle.
This solution is really long.
Greedy solution
We can continuously take a leaf and pair it with its parent. Here's why:
Let
Unable to parse markup [type=CF_MATHJAX]
$ be a leaf and
Unable to parse markup [type=CF_MATHJAX]
$ its parent. Consider an optimal set
Unable to parse markup [type=CF_MATHJAX]
$.
- If
Unable to parse markup [type=CF_MATHJAX]
$ is already in
Unable to parse markup [type=CF_MATHJAX]
$, we should take it. - Otherwise, there is an edge
Unable to parse markup [type=CF_MATHJAX]
$ that we can replace with
Unable to parse markup [type=CF_MATHJAX]
$, keeping the result the same.
Therefore, taking
Unable to parse markup [type=CF_MATHJAX]
$ always gives an optimal answer.
We use indegree peeling to peel off the trees. Now, what about the cycles?
If a cycle remains, the optimal solution for each attached tree must have its root colored white. This means we can freely take nodes from the cycle without affecting the optimality of the solution.
In a cycle, no two black nodes (nodes receiving supervision) can be adjacent. Therefore, the maximum number of nodes we can color black is cycle_length / 2.
7. Kattis — GCD Harmony
One possible solution is to change all nodes to
Unable to parse markup [type=CF_MATHJAX]
$, which means we only need to keep values from
Unable to parse markup [type=CF_MATHJAX]
$ to
Unable to parse markup [type=CF_MATHJAX]
$ in our DP.
This is a knapsack-on-trees problem: we perform knapsack for each connection. However, that would take
Unable to parse markup [type=CF_MATHJAX]
$ time.
We can make the following observations:
- When changing
Unable to parse markup [type=CF_MATHJAX]
$ to another value, we do not need to consider values containing a squared prime factor, such as
Unable to parse markup [type=CF_MATHJAX]
$, because we only need
Unable to parse markup [type=CF_MATHJAX]
$. - During each transition, we do not need to try every value. When changing
Unable to parse markup [type=CF_MATHJAX]
$ to some value
Unable to parse markup [type=CF_MATHJAX]
$, that value must share a prime factor with the value we are transitioning from. Therefore, we only need to iterate through the distinct prime factors of
Unable to parse markup [type=CF_MATHJAX]
$.
This reduces the complexity from
Unable to parse markup [type=CF_MATHJAX]
$ to around
Unable to parse markup [type=CF_MATHJAX]
$-ish, or at most about
Unable to parse markup [type=CF_MATHJAX]
$ operations.
More Problems
Thank you for reading!



