Dp on Trees

Revision en4, by theoneandonlytron, 2026-11-16 06:05:02

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]: Sum dp[child][2] over all children.
  • dp[i][1]: Sort the children by dp[child][2] - dp[child][1] to find the greatest improvement, then take children[0].
  • dp[i][2]: Use the same idea as dp[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 minimum dp[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] and visited[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!

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English theoneandonlytron 2026-11-16 06:17:57 301
en5 English theoneandonlytron 2026-11-16 06:07:47 509 (published)
en4 English theoneandonlytron 2026-11-16 06:05:02 17229
en3 English theoneandonlytron 2026-11-16 05:37:43 3699
en2 English theoneandonlytron 2026-11-16 05:07:14 3670
en1 English theoneandonlytron 2026-11-16 00:45:09 499 Initial revision (saved to drafts)