Tree DP

DP where the state is a subtree. The dependency order is post-order: a vertex is computed after all of its children.

The skeleton

void dfs(int u, int p) {
    dp[u] = base(u);
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        dp[u] = combine(dp[u], dp[v]);
    }
}

Everything else is choosing what dp[u] means and how combine works.

Canonical examples

Maximum independent set on a tree

dp[u][0] = best in $u$ ‘s subtree with $u$ not chosen; dp[u][1] = with $u$ chosen.

void dfs(int u, int p) {
    dp[u][0] = 0; dp[u][1] = w[u];
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        dp[u][0] += max(dp[v][0], dp[v][1]);
        dp[u][1] += dp[v][0];                  // v cannot be chosen
    }
}
// answer: max(dp[root][0], dp[root][1])

The [0/1] second dimension — “is this vertex used” — is the most common tree-DP pattern.

Longest path (diameter) through a vertex

Track the two deepest downward paths and combine them at each vertex. See Tree Diameter.

Counting subtrees / paths

dp[u] = number of ways within $u$ ‘s subtree; combine by multiplication or by the “knapsack on tree” merge below.

Tree knapsack — the size-bounded merge

When the state is dp[u][k] (“best using $k$ vertices from $u$ ‘s subtree”), the naive merge looks $O (n^{2})$ per vertex, but bounding the loops by the actual subtree sizes makes the total $O (n^{2})$ over the whole tree:

void dfs(int u, int p) {
    sz[u] = 1;
    dp[u][0] = 0; dp[u][1] = w[u];
    for (int v : adj[u]) {
        if (v == p) continue;
        dfs(v, u);
        for (int i = min(sz[u], K); i >= 0; i--)
            for (int j = min(sz[v], K - i); j >= 0; j--)
                tmp[i + j] = max(tmp[i + j], dp[u][i] + dp[v][j]);
        sz[u] += sz[v];
        copy back into dp[u];
    }
}

Why it is $O (n^{2})$ and not $O (n^{3})$ : every pair of vertices is “merged” exactly once, at their LCA. The nested loops therefore count pairs, and there are $(2 n)$ of them. Capping at $K$ improves it further to $O (n K)$ .

Getting the loop bounds right (min(sz[u], K), not K) is what makes this work — with fixed bounds it really is $O (n K^{2})$ .

The patterns

Problem	State
Maximum independent set	`dp[u][0/1]`
Minimum vertex cover	`dp[u][0/1]`
Tree colouring with $k$ colours	`dp[u][c]`
Longest path in a subtree	two deepest depths
Count paths of length $k$	`dp[u][d]` = vertices at depth $d$ in the subtree (merge small-to-large)
Choose exactly $k$ vertices	`dp[u][k]` tree knapsack
Distances to all vertices	rerooting
Matching on a tree	`dp[u][0/1]` = is $u$ matched to a child
Distinct colours per subtree	DSU on tree or Euler tour + offline
Delete edges to satisfy a constraint	`dp[u][state]` with the constraint in the state

Small-to-large merging

When each vertex holds a set or map rather than a fixed-size array, merge the smaller structure into the larger:

if (mp[u].size() < mp[v].size()) swap(mp[u], mp[v]);
for (auto& [k, val] : mp[v]) mp[u][k] += val;
mp[v].clear();

Each element moves $O (lo g n)$ times, so the total is $O (n lo g n)$ merges (times the map’s own $lo g$ ). This is how “count distinct values in each subtree” and similar problems get an efficient solution without any heavy machinery. See DSU on Tree.

Iterative tree DP

For deep trees, compute an order once and then process it in reverse:

vector<int> order; order.reserve(n);
stack<int> st; st.push(root); par[root] = -1;
while (!st.empty()) {
    int u = st.top(); st.pop(); order.push_back(u);
    for (int v : adj[u]) if (v != par[u]) { par[v] = u; st.push(v); }
}
for (int i = n - 1; i >= 0; i--) { int u = order[i]; /* combine children of u */ }

Reverse BFS/DFS order is post-order for the purposes of aggregation, and it never overflows the stack.

See also: Rerooting DP · DSU on Tree · Tree Fundamentals

whoashish's cp notes

Directory