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 n children:
- The first child contributes
2. - Each additional child adds another
2.
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 2.
We can formulate the DP using these states:
dp[i][0]: Nodeiis not part of any star.dp[i][1]: Nodeiis a child of a star.dp[i][2]: Nodeiis 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 2 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]: Keep0edges.dp[i][1]: Keep1edge.dp[i][2]: Keep2edges.
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 tod[i] - 1edges leading to children.dp[i][1]: Connect tod[i]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 k, 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 k, then k must be a factor of n - 1. Therefore, we only need to traverse each i 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 i to F[i]. If we perform an operation on node i, we can consider the following cases:
- Connect it to some other node
j. That node must connect to itself, costingC[i] + C[j]. This is not optimal because we could simply connect nodeito itself forC[i]. - Connect node
ito itself, costingC[i]. - Perform an operation on
F[i]to connect it to itself, costingC[F[i]].
In the end, there are only two operations to consider: performing an operation on i or on F[i].
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]:4MB.dp[i][2]andcost[i][2]:16MB.vector<vector<ll>> adj: Absolutely over the limit.
We can optimize the adjacency list using a condensed edge array, keeping Start and Arr for 8 MB. For each node, we store the range [L, R] 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 0. 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 u be a leaf and v its parent. Consider an optimal set S.
- If
(u, v)is already inS, we should take it. - Otherwise, there is an edge
(v, w)that we can replace with(u, v), keeping the result the same.
Therefore, taking (u, v) 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 2, which means we only need to keep values from 1 to 2N in our DP.
This is a knapsack-on-trees problem: we perform knapsack for each connection. However, that would take N * 4N^2 = 4N^3 time.
We can make the following observations:
- When changing
a[i]to another value, we do not need to consider values containing a squared prime factor, such as2^2 * 3, because we only needgcd(a[i], a[j]) > 1. - During each transition, we do not need to try every value. When changing
a[i]to some valuej, 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 ofj.
This reduces the complexity from 4N^3 to around N^2 * 6 * 1.2-ish, or at most about 2 * 10^8 operations.
More Problems
Thank you for reading!



