Dynamic Programming • Pattern

DP on Trees

Explore how to compute optimal solutions on tree data structures using Post-Order DFS traversal and state aggregation.

Overview

Trees are natural recursive structures. A subtree is completely independent of the rest of the tree, which is perfect for DP.

To solve a node `u`, we must first solve all its children `v`. This strictly requires a post-order traversal (DFS).

As the recursion unwinds, the parent aggregates the states returned by its children to form its own state.

Sometimes the global answer is not at the root. We often maintain a global `maxAns` variable that is updated during every node's processing.

0

1

2

3

4

Code Tracker

:::

1function dfs(u, parent) {

2 for (let v of adj[u]) {

3 if (v === parent) continue;

4 dfs(v, u);

5 // Update dp[u] using dp[v]

6 }

7 // Finalize dp[u] state

8}