DP on Trees

Tree DP is just dynamic programming where each node’s answer depends on its children’s answers (after we pick a root).

In its most basic form:

Root the tree (pick a node as the root)
Do a DFS
While returning from DFS (bottom-up), compute DP values for each node using its children

Why this works: Once a tree is rooted, each node “controls” its own subtree, and subtrees don’t overlap. So you can solve each subtree once and combine results.

Simple Task: Maximum Independent Set

Pick as many nodes as possible such that:

you never pick two adjacent nodes (no edge has both ends picked)

Example

If you pick node v, you are forced to NOT pick all neighbors of v.

In a rooted tree, the important neighbors are:

the parent
the children

So the problem becomes a simple choice at each node:

pick this node → you must skip all children
skip this node → each child can be picked or skipped, whichever is better

DP States (Two numbers per node)

For every node v:

dp1[v]: best answer in the subtree of v if v IS chosen
dp0[v]: best answer in the subtree of v if v is NOT chosen

“Subtree of v” means v and all descendants under it (after rooting).

Transitions (How to compute them)

Suppose we are at node v and we already computed DP for all children.

Case 1: `v` is chosen

Then no child can be chosen.

So for each child c, we must use dp0[c].

dp1[v] = 1 + sum(dp0[c] for all children c)

1 because we count node v itself
children must be in “not chosen” state

Case 2: `v` is NOT chosen

Then each child c is free:

either choose c (get dp1[c])
or skip c (get dp0[c])

We take the best option for each child independently:

dp0[v] = sum( max(dp0[c], dp1[c]) for all children c )

Final Answer

For the whole tree, at the root, we can either choose it or not:

answer = max(dp0[root], dp1[root])

Implementation (DFS)

int n;
vector<vector<int>> g;

vector<int> dp0, dp1;

void dfs(int v, int p) {
    dp1[v] = 1;  // choose v
    dp0[v] = 0;  // don't choose v

    for (int to : g[v]) {
        if (to == p) continue;
        dfs(to, v);

        // if we choose v, we must NOT choose child
        dp1[v] += dp0[to];

        // if we don't choose v, child can be either
        dp0[v] += max(dp0[to], dp1[to]);
    }
}

Usage:

int root = 0;
dp0.assign(n, 0);
dp1.assign(n, 0);

dfs(root, -1);

int ans = max(dp0[root], dp1[root]);

Tiny Walkthrough Example

Say v has two children: a and b.

And you already computed:

dp0[a] = 3, dp1[a] = 4
dp0[b] = 2, dp1[b] = 2

Then:

If you choose v:

you must skip a and b

dp1[v] = 1 + dp0[a] + dp0[b] = 1 + 3 + 2 = 6

If you skip v:

you choose best for each child

dp0[v] = max(3,4) + max(2,2) = 4 + 2 = 6

So both ways give 6 here.

What to remember (Tree DP pattern)

Most tree DP problems look like this:

pick a root
define DP states per node
DFS to compute children first
combine children results with simple formulas

But as problems get more complex, more complex designs might be needed.

A very common design is exactly what you saw:

state = “take node” vs “skip node”