Dynamic Programming8 min read

DP on Trees

Each node's answer depends on its children — compute bottom-up
standard tree DP:\(O(n)\)tree knapsack:\(O(n^2)\)rerooting technique:\(O(n)\)

Imagine calculating a sports team's total score where each player's contribution depends on the players directly below them in the hierarchy — coaches depend on their assistants, assistants depend on their players. To compute the head coach's score, you first need every player's score, then every assistant's, and only then the coaches'. That bottom-up aggregation is exactly DP on Trees.

Trees have no cycles, which means the parent-child direction gives you a natural computation order. Process children before parents — that's DFS post-order. When you arrive at a node, all its children's DP values are already ready.

Basic Tree DP: Post-Order DFS

Root the tree at any node. In post-order DFS, a node is visited only after all its subtree descendants. So when you compute dp[node], every dp[child] is already available. The DP state dp[node] typically represents "the best answer for the subtree rooted at node".

Example — Maximum Path Sum: dp[node] = max sum of a downward path starting at this node. dp[node] = node.val + max(0, max(dp[child] for all children)). The overall answer might pass through a node as the highest point — sum up its two best child paths to find the diameter or max path.

Tree Knapsack — Selecting a Connected Subtree

Select at most k nodes from the tree to maximize total value, with the rule: if a node is selected, its parent must also be selected (the selected nodes form a connected subtree). State: dp[node][j] = max value using exactly j nodes from node's subtree, including node itself. Merge children one by one using a knapsack-style combination. With careful implementation, total time is \(O(n^2)\).

Rerooting — When Every Node Needs to Be the Root

Sometimes dp[node] should represent the answer for the whole tree when node is the root, not just its subtree. Computing this naively (re-root and re-run DFS for every node) is \(O(n^2)\).

The rerooting technique does it in two DFS passes:

Down-pass (DFS 1): Root at node 0, compute down[v] = subtree answer for v.

Up-pass (DFS 2): For each node v, compute up[v] = the best answer from outside v's subtree (from v's parent and the parent's other children). Combine down[v] and up[v] to get the full-tree answer rooted at v.

Example — Sum of Distances: For every node, find the total distance to all other nodes. Two DFS passes compute this for all n nodes in \(O(n)\) total.

Note: Tree DP is powerful because the tree structure eliminates cycles — there's always a clear direction to compute states. If you ever get confused about order, just ask: 'Does a parent depend on its children, or children on their parent?' That tells you which DFS direction to use.

Tree DP — diameter of a tree

from collections import defaultdict


def tree_diameter(n, edges):
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)


    diameter = [0]


    def dfs(node, parent):
        # returns longest downward path from node
        best1 = best2 = 0  # two longest child paths
        for child in graph[node]:
            if child == parent:
                continue
            d = dfs(child, node) + 1
            if d >= best1: best1, best2 = d, best1
            elif d > best2: best2 = d
        diameter[0] = max(diameter[0], best1 + best2)
        return best1


    dfs(0, -1)
    return diameter[0]


print(tree_diameter(5, [(0,1),(1,2),(2,3),(1,4)]))  # 3
print(tree_diameter(4, [(0,1),(1,2),(1,3)]))         # 2
Output
3
2

Complexity

🌳 Standard tree DP (single DFS)Post-order DFS; each edge traversed exactly twice
Visit each node once\(O(n)\)
🎒 Tree knapsack (select k connected nodes)Merging subtree tables costs \(O(size_1 × size_2)\) per merge; total across all merges = \(O(n^2)\)
Quadratic with careful merge\(O(n^2)\)
🐌 Naive rerooting (DFS per root)Running a full DFS for every possible root is \(O(n)\) × \(O(n)\) = \(O(n^2)\)
Quadratic\(O(n^2)\)
⚡ Rerooting (2-pass DFS)Down-pass computes subtree answers; up-pass propagates rest-of-tree answer to each node
Two linear passes\(O(n)\)
📏 Tree diameterTrack the two longest child paths at each node; update global max at every node
Single DFS or two BFS\(O(n)\)

Quick check

Why is DFS post-order the natural traversal for tree DP?

Continue reading

DP Pattern
Never solve the same puzzle piece twice — write it down and look it up next time
→
BFS & DFS Revisited
Two ways to explore a graph — level by level, or all the way in
→