Skip to main content

Tree DP: Independent Set, Diameter, Rerooting

What This Concept Is​

Tree DP computes answers at each node by combining answers from its children. The state space is indexed by tree node (plus, usually, a small additional dimension). The natural fill order is post-order DFS: each $dp[v]$ depends only on its already-computed children. Three patterns cover most cases:

  • Subtree DP. Root the tree arbitrarily; compute $dp[v]$ from $dp[c]$ for each child $c$. Example: maximum independent set on a tree, subtree sum, count leaves, max depth.
  • Diameter / two-best. At each node, combine the two best root-to-leaf depths through it. The diameter is the maximum, over all nodes, of (first-best depth) + (second-best depth). Generalizes to "any two paths meeting at $v$."
  • Rerooting (dp_all). Compute an answer for every node as root, in $O(n)$ total, by reusing the subtree-DP computed at one fixed root. Uses a second DFS that propagates "contribution from the rest of the tree" downward. Without rerooting, the naive approach is $n$ separate DFSes, $O(n^2)$.

The common shape:

def dfs(v, parent):
    for c in neighbors[v]:
        if c != parent:
            dfs(c, v)
            # combine dp[c] into dp[v]
    # finalize dp[v]

Trees have two properties that make DP especially clean: $n - 1$ edges (no cycles), and a natural recursive structure (every subtree is itself a tree). DP on general graphs is harder precisely because cycles break the "compute children first" ordering.

Why It Matters Here​

Trees are everywhere: parse trees, dependency graphs, file systems, game trees, taxonomies, version-control merge bases. Tree DP is the natural way to compute optimal selections, costs, or counts that respect the parent-child structure. It is also the simplest non-trivial DP that departs from the "1D array of states" mental model -- the state is per node, and the fill order is structural (topological on the DFS tree), not index-based.

The rerooting technique is the single most useful "advanced" idea in this cluster: it converts "compute X for every possible root" from $O(n \cdot T)$ to $O(n)$ where $T$ is a per-root DFS cost. It shows up repeatedly in competitive programming and in practical problems like "for each server, sum distances to all other servers."

Concrete Examples​

Maximum independent set on a tree. An independent set is a set of vertices with no two adjacent. For each vertex $v$, define:

  • $dp[v][0]$ = max size of an independent set in the subtree rooted at $v$, where $v$ is not included
  • $dp[v][1]$ = max size where $v$ is included

Recurrences:

$$dp[v][1] = 1 + \sum_{c ,\in, \mathrm{children}(v)} dp[c][0]$$

$$dp[v][0] = \sum_{c ,\in, \mathrm{children}(v)} \max\big(dp[c][0],\ dp[c][1]\big)$$

Answer: $\max(dp[\mathrm{root}][0], dp[\mathrm{root}][1])$.

For the tree

      1
     / \
    2   3
   / \
  4   5

all edges unit weight, the MIS size is $3$ (e.g., ${4, 5, 3}$). Verify: $dp[4] = (0, 1)$, $dp[5] = (0, 1)$, $dp[2] = (2, 1)$ (take $4, 5$ without $2$, or take $2$ alone), $dp[3] = (0, 1)$, $dp[1] = (3, 2)$. Max is $3$.

Tree diameter (number of edges on the longest path). Single DFS from any root. At each node, let $\mathrm{best_1}[v], \mathrm{best_2}[v]$ be the two largest among $\mathrm{depth}(c) + 1$ across children $c$. Update $\mathrm{answer} = \max(\mathrm{answer}, \mathrm{best_1}[v] + \mathrm{best_2}[v])$. Return the answer after DFS.

Rerooting -- sum of distances. Problem: for each vertex $v$, compute $\sum_{u} \mathrm{dist}(v, u)$.

First DFS from root $0$: $\mathrm{cnt}[v]$ = subtree size, $\mathrm{sum}[v]$ = sum of distances from $v$ to all descendants. Then second DFS: when moving root from $p$ to $c$, subtree of $c$ gets closer by 1 ($\mathrm{cnt}[c]$ vertices) and the rest gets farther by 1 ($n - \mathrm{cnt}[c]$ vertices). So $\mathrm{ans}[c] = \mathrm{ans}[p] - \mathrm{cnt}[c] + (n - \mathrm{cnt}[c])$. $O(n)$ total.

MIS top-down memoized form (same recurrence, equivalent cost):

@lru_cache(None)
def f(v, take):
    total = 1 if take else 0
    for c in children[v]:
        if take:
            total += f(c, False)
        else:
            total += max(f(c, True), f(c, False))
    return total
answer = max(f(root, True), f(root, False))

Distinct states: $2n$, one per (node, take?) pair. The cache serves the role of the explicit $dp[v][0..1]$ table.

Common Confusion / Misconceptions​

"Recurse into the parent." The first-time trap. In an undirected tree represented as an adjacency list, every node lists its parent as a neighbor. Always pass parent to the DFS and skip it, or use a visited flag.

"Tree DP must go bottom-up." Subtree DP does. But rerooting is explicitly top-down after bottom-up: a second DFS pushes information from parent into children. Missing this is why students reinvent $O(n^2)$ solutions.

"Picking any root is fine." It is for root-invariant quantities (MIS size, diameter). It is not for root-dependent ones (sum of distances, "best leaf reachable from each node"). For the latter, you need rerooting or a different formulation.

"Tree DP needs two states per node." MIS does because of the "included vs not" case-split. But tree DP in general uses whatever state the recurrence needs: 1 per node (subtree sum), 2 per node (MIS, matching), $O(n)$ per node (small-to-large merging for subtree statistics). Size the state to the problem.

"Iterative DFS is always faster." For $n \ge 10^5$, recursion may stack-overflow in some languages (Python's default is $10^3$). Either switch to iterative DFS (explicit stack, post-order via two passes or Euler tour) or raise the recursion limit deliberately.

How To Use It​

  1. Root the tree at an arbitrary vertex (often $0$ or $1$).
  2. Define the state $dp[v][\ldots]$ and its meaning in terms of the subtree rooted at $v$.
  3. Write the recurrence in terms of $dp[c][\ldots]$ for children $c$.
  4. Post-order DFS fills $dp$.
  5. Combine at the root (or at the best node) for the final answer.
  6. For "for each root" questions, do a rerooting DFS: first pass subtree DP, second pass propagate "rest of tree" contribution.
  7. Watch stack depth. For $n \ge 10^5$, either raise recursion limit or use iterative DFS.

Transfer / Where This Shows Up Later​

  • S3 Software Design. Composite pattern evaluation (aggregate child contributions into parent) is tree DP with a specific combine operation. Visitors are the OO encoding of the DFS.
  • S5 Networking. Multicast tree optimization -- route a stream to many subscribers with minimum total edge cost -- uses tree DP (Steiner tree variants, aggregated bandwidth).
  • S6 Databases. Query plans are trees; cost models aggregate child operator costs into the parent with tree DP. Index selection on a schema tree is the same shape.
  • S7 Architecture. Dependency-graph analysis (when the graph is a DAG or tree) -- "sum of fan-out across a service tree" -- is a rerooting DP on the architecture graph.
  • Phase 7 AI. Minimax and Expectimax on game trees are tree DPs with alternating max/min (or expectation) at the combine step. Monte Carlo Tree Search explores the same DP with sampling.

Check Yourself​

  1. Why does the MIS recurrence need two states per node, not one?
  2. How does rerooting avoid running a full DFS once per vertex?
  3. For tree diameter, why are the two best child depths enough, not just the single best?
  4. Give a tree DP that is root-invariant and one that is root-dependent.
  5. Sketch the rerooting transition for "maximum depth of any leaf from root $v$."
  6. How do you convert a recursive tree DP into an iterative one for $n = 10^6$?

Mini Drill or Application​

  1. Implement MIS on a tree with $n = 10^5$ nodes; test on a path and on a complete binary tree.
  2. Implement tree diameter two ways: (a) single-DFS two-best recurrence; (b) two-DFS "farthest from arbitrary vertex, then farthest from that" method. Verify they agree.
  3. Implement "sum of distances" via rerooting; test on a small tree against a brute-force $O(n^2)$ BFS-from-each-node reference.
  4. Implement weighted MIS: each vertex $v$ has weight $w[v]$; maximize total weight of an independent set.
  5. Tree path cover (min paths to cover all vertices) via tree DP.
  6. "Cat-and-mouse on a tree": given a starting position for each, compute whether the cat catches the mouse; tree DP over pairs of positions.

Read This Only If Stuck​