No history yet

Tree Dynamic Programming

Solving Problems on Trees

Many tree problems involve calculating some optimal value, like the longest path or the largest possible subset of nodes with a certain property. A brute-force approach, checking every possibility, is usually too slow. This is where dynamic programming comes in.

On a tree, the subproblems are naturally defined by subtrees. If you root the tree arbitrarily (say, at node 1), every node u becomes the root of its own subtree. The core idea of Tree DP is that the solution for a node u can often be calculated by combining the pre-computed solutions for its children. This structure lends itself perfectly to a Depth-First Search (DFS). We compute answers for the leaves first and work our way up to the root.

Subtree States

The first step is defining the 'state' of our DP. A state is simply the information we need to compute for each subtree to solve the larger problem. Let's use the problem as an example: find the largest subset of nodes in a tree such that no two nodes in the subset are connected by an edge.

For any node u, we have two choices: either include u in our set or don't. This suggests our DP state needs to capture both possibilities for the subtree rooted at u.

Let's define two states:

  • dp[u][1]: The size of the maximum independent set in the subtree of u, including node u itself.
  • dp[u][0]: The size of the maximum independent set in the subtree of u, excluding node u.

Now, how do we calculate these values? We use a DFS. When our traversal reaches node u, we first recursively call it on all of u's children. Once those calls return, we have the dp values for all children, and we can compute dp[u].

The logic, or 'transition,' works like this:

  1. To calculate dp[u][1] (we include u): If we take u, we cannot take any of its direct children. So, for each child v, we must choose the option where v is not included. We add up dp[v][0] for all children v and add 1 for u itself.

  2. To calculate dp[u][0] (we exclude u): If we don't take u, we are free to make the best choice for each child v's subtree independently. For each child v, we can either include it (dp[v][1]) or not (dp[v][0]). We take the maximum of these two options and add it to our total.

dp[u][1]=1+∑v∈children(u)dp[v][0]dp[u][0]=∑v∈children(u)max⁡(dp[v][0],dp[v][1])\begin{aligned} dp[u][1] &= 1 + \sum_{v \in children(u)} dp[v][0] \\ dp[u][0] &= \sum_{v \in children(u)} \max(dp[v][0], dp[v][1]) \end{aligned}

After the DFS completes for the entire tree, the final answer is the best we can do for the root (node 1), which is max(dp[1][0], dp[1][1]).

// Adjacency list for the tree
vector<int> adj[N];
// DP table
int dp[N][2];

void dfs(int u, int p) {
    // Base case: initialize values for node u
    dp[u][1] = 1; // Include u
    dp[u][0] = 0; // Exclude u

    for (int v : adj[u]) {
        if (v == p) continue; // Don't go back up
        
        // Recursively solve for child v
        dfs(v, u);

        // Combine results from child v
        dp[u][1] += dp[v][0];
        dp[u][0] += max(dp[v][0], dp[v][1]);
    }
}

// To run:
// dfs(1, 0); // Start from root 1, with parent 0
// int answer = max(dp[1][0], dp[1][1]);

Changing the Root

Sometimes, a problem asks for an answer calculated for every node as if it were the root of the tree. For example, for each node u, what is the size of the largest sub-component if we remove u? Or, what is the length of the longest path starting from u?

Running a full DFS from every single node would be O(N2)O(N^2), which is too slow for large N. We need a more efficient method. This is where comes in. It's a powerful technique that uses two DFS passes to get the answer for all nodes in O(N)O(N) time.

Pass 1: Bottom-Up DFS

First, we pick an arbitrary root (let's use node 1) and run a standard post-order DFS. In this pass, we compute values for each node u based only on the information from its children in the rooted tree. Let's stick with our longest path example. We'll compute down[u], the length of the longest path starting at u and going down into its subtree.

Pass 2: Top-Down DFS

The second pass is a pre-order DFS, again starting from the root. This time, we calculate information for a child v based on information from its parent u. We'll compute up[v], the length of the longest path starting at v and going upwards (away from its own original subtree).

How do we calculate up[v]? The path starting at v and going up must first go to its parent, u. From u, the path can either continue further up (using the up[u] value we've already computed) or go down into one of v's sibling's subtrees. We take the best of these options.

up[v] = 1 + max(up[u], longest_down_path_from_u_not_using_v)

With both down[u] and up[u] for every node u, we can find the answer. The longest path starting at u is simply max(down[u], up[u]). The true diameter of the tree is the maximum value of down[u] + up[u] across all nodes u, but this calculation is a bit more nuanced. A simpler approach for diameter is to combine the top two longest downward paths at each node during the first DFS.

This two-pass pattern is incredibly versatile. It can be adapted to solve a wide range of problems where each node's answer depends on its relationship to the entire tree, not just its descendants.

Quiz Questions 1/5

What is the fundamental principle behind Dynamic Programming on trees?

Quiz Questions 2/5

In the context of the Maximum Independent Set problem on a tree, what does the state dp[u][1] typically represent?

Tree DP combines the recursive nature of trees with the optimization power of dynamic programming. By defining states on subtrees and combining results using a DFS, we can solve complex problems far more efficiently than with a brute-force approach.