Lesson 13 · Problem-solving methods

Tree Dynamic Programming

Tree DP roots an acyclic graph so each node combines independent child subproblems, with rerooting when answers are needed for every possible root.

Why trees decompose cleanly

Removing an edge from a tree separates it into independent components. After choosing a root, a node’s subtree shares no vertices with a sibling subtree, so child answers can be combined without double counting. The parent parameter prevents traversing the undirected edge backward.

The root is an algorithmic orientation, not a change to the input. Choose any root for root-invariant problems; for directed or semantically rooted trees, preserve the specified direction.

Cut edges separate subproblems
Parent checks replace a visited set
Root choice may be arbitrary

Designing node states

Independent-set DP uses take[u] and skip[u]. Taking u forces every child to skip; skipping u allows each child’s better choice. Other tree states describe subtree size, selected-edge status, path endpoints, or constrained colors.

State must include every interaction crossing the parent edge. If the parent only needs to know whether u is selected, two states suffice; adding grandchild history bloats the table without affecting future choices.

States summarize the parent boundary
Children combine independently
Minimal state improves clarity and speed

Key reference

Terms, operations, and practical uses

Tree states

Rooted treeRooted tree is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Parent parameterParent parameter is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Subtree answerSubtree answer is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Traversal

PostorderPostorder is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Take stateTake state is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Skip stateSkip state is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Extensions

RerootingRerooting is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
Prefix/suffix combinePrefix/suffix combine is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.
ReconstructionReconstruction is a topic-specific concept used by the algorithm and is explained in the lesson's mechanism, proof, or implementation.

Implementation

Tree DP combines take and skip states

g=[[1,2],[0,3,4],[0],[1],[1]]
def dfs(u,p):
    take,skip=1,0
    for v in g[u]:
        if v==p:continue
        a,b=dfs(v,u);take+=b;skip+=max(a,b)
    return take,skip
a,b=dfs(0,-1);print("Maximum independent set:",max(a,b))

#include <algorithm>
#include <array>
#include <cstring>
#include <functional>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;
vector<vector<int>> g={{1,2},{0,3,4},{0},{1},{1}};
pair<int,int> dfs(int u,int p) {
    int take=1,skip=0;
    for(int v:g[u]) if(v!=p) {
        auto [a,b]=dfs(v,u);
        take+=b;
        skip+=max(a,b);
    }
    return {take,skip};
}
int main() {
    auto [a,b]=dfs(0,-1);
    cout << "Maximum independent set: " << max(a,b) << '\n';
}

import java.util.*;
class Main {
    static int[][] g={{1,2},{0,3,4},{0},{1},{1}};
    static int[] dfs(int u,int p) {
        int take=1,skip=0;
        for(int v:g[u]) if(v!=p) {
            int[] x=dfs(v,u);
            take+=x[1];
            skip+=Math.max(x[0],x[1]);
        }
        return new int[]{take,skip};
    }
    public static void main(String[] args) {
        int[] x=dfs(0,-1);
        System.out.println("Maximum independent set: "+Math.max(x[0],x[1]));
    }
}

Watch it run

Step through it

Running on tree edges 0-1,0-2,1-3,1-4

Output

Postorder evaluation

Recursive DFS naturally computes children before the parent’s combine step. An iterative version records parent/order with a stack, then processes that order backward. Both run O(V) when each edge and each constant-size state is handled once.

Deep chains can overflow recursion limits, so iterative postorder is not merely stylistic. Use wide totals when many child contributions accumulate and define leaves through the identity of the combine operation.

Children finish before parents
Reverse traversal order gives postorder
Chains expose recursion limits

Rerooting for every vertex

A subtree pass computes contributions from below. A second pass sends each child the contribution from its parent side, often using prefix and suffix aggregates to exclude that child without division. Then every node combines below and above as if it were root.

This converts an O(V²) restart-from-every-root approach into O(V) or O(V·state). The transition from parent to child must remove the child’s old contribution before adding the new outside contribution.

First pass computes down values
Second pass propagates up values
Prefix/suffix excludes one child safely

Validation and non-tree inputs

Test one node, a chain, a star, negative weights, and ties. Verify parent-child orientation and compare small cases with subset brute force. A cycle destroys subtree independence and can cause infinite recursion or double counting.

If the input may be a forest, start a root in each component and combine component answers according to the problem. Confirm E=V−components before calling a general graph a forest.

Cycles violate the decomposition
Forests need one root per component
Brute force validates small trees

Reconstruction and reroot safety

To recover a selected set, store which child state achieved each optimum or recompute decisions while descending from the chosen root state. Ties need deterministic handling if examples or tests expect one specific set. The value recurrence alone does not identify the chosen vertices.

For noncommutative combines, child order matters and prefix/suffix rerooting must preserve it. For diameter-like states, retain the best two child contributions rather than only the maximum. Write the exact summary the parent needs before optimizing the traversal.

When weights may be negative, clarify whether selecting nothing is allowed; identity zero can otherwise defeat a required nonempty solution. For forests, combine component optima according to independence and ensure the traversal does not assume vertex zero reaches every node.

Proofs usually follow structural induction. Assume every child state correctly summarizes its child subtree; because distinct child subtrees share no vertices, the parent may combine those summaries according to whether the parent is selected. This independence is exactly what fails on a general graph with cycles. In code, an explicit parent parameter is often cheaper than rebuilding a directed tree, but iterative postorder is safer when the tree can be a long chain. Confirm that the input really is a tree—connected with N−1 edges—or add a visited set. Otherwise a parent-only guard cannot prevent recursion around a longer cycle.

Store choices for reconstruction
Preserve order for noncommutative combines
Some states need the top two children