DP on Trees and Rerooting

Why a tree is a DP's best friend

The previous guide put a DP on a line of indices — an interval. A tree is the next shape up, and it turns out to be just as friendly. A tree is a connected graph with no cycles, so if you pick any node to be the root, every other node has exactly one parent and the whole structure hangs downward into nested subtrees. That nesting is precisely the optimal substructure a DP wants: the answer for a node is assembled from the answers for its children, and a child's subtree never reaches back up to touch its parent. There are no cycles to create circular dependencies, so the subproblems form a clean partial order.

This is why DP on trees is one of the cleanest design patterns you will meet. The natural way to visit the nodes is a depth-first search from the root: descend to the leaves, then let answers bubble back up. Because a child is fully solved before its parent needs it, the visiting order — post-order, children before parent — is automatically a valid evaluation order. You never have to hand-design a table-filling sequence the way you did for the interval DP; the recursion itself walks the dependency order for free.

The one-pass subtree recurrence

Let us make it concrete with a classic: the maximum weighted independent set on a tree. Each node carries a weight, and we want to pick a set of nodes with the largest total weight such that no two chosen nodes are adjacent (no chosen parent-child pair). Defining the state is the whole art, and here it has two parts. For each node v we keep two answers: down[v][0], the best total inside v's subtree when v is NOT taken, and down[v][1], the best total inside v's subtree when v IS taken. Keeping both possibilities is what lets the parent decide cleanly.

Now the transition writes itself from the adjacency rule. If v is NOT taken, each child c is free to be taken or not, so we add the better of the two for every child. If v IS taken, no child may be taken, so we are forced into the 'not taken' branch for each child and add v's own weight. In compact form: down[v][0] = sum over children c of max(down[c][0], down[c][1]); and down[v][1] = weight(v) + sum over children c of down[c][0]. The answer for the whole tree is max(down[root][0], down[root][1]).

function dfs(v, parent):
    down[v][0] = 0
    down[v][1] = weight[v]
    for c in neighbors[v]:
        if c == parent: continue        # don't walk back up
        dfs(c, v)                        # solve the child first
        down[v][0] += max(down[c][0], down[c][1])
        down[v][1] += down[c][0]
# answer = max(down[root][0], down[root][1])

Why is this correct? By induction up the tree: at a leaf the formulas are trivially right (down[leaf][0]=0, down[leaf][1]=weight), and at an internal node, IF every child's two answers are already optimal, then the max/sum above is the best the node can do given its own binary choice. The cost is honest and easy to read: the loop body runs once per parent-child edge, a tree on n nodes has exactly n-1 edges, and each step is O(1), so the entire computation is O(n) time and O(n) space. That linear bound is the headline reward for the no-cycles structure.

A tiny trace

Take a five-node tree: root A (weight 3) has children B (weight 4) and C (weight 1); B in turn has children D (weight 2) and E (weight 5). The leaves D, E, C are solved first. For each leaf, the 'not taken' answer is 0 and the 'taken' answer is its own weight, so down[D]=(0,2), down[E]=(0,5), down[C]=(0,1). Nothing surprising yet — a leaf's subtree is just itself.

1. Node B combines D and E. down[B][0] = max(0,2) + max(0,5) = 2 + 5 = 7 (B skipped, both children free to be taken). down[B][1] = weight(B) + down[D][0] + down[E][0] = 4 + 0 + 0 = 4 (B taken, so D and E forced off). So down[B] = (7, 4).
2. Node A combines B and C. down[A][0] = max(7,4) + max(0,1) = 7 + 1 = 8. down[A][1] = weight(A) + down[B][0] + down[C][0] = 3 + 7 + 0 = 10. So down[A] = (8, 10).
3. The whole-tree answer is max(8, 10) = 10, achieved by taking A, D, and E (weights 3 + 2 + 5), none of them adjacent. Reading off WHICH nodes was the easy part here; in general you recover it by reconstructing the solution, walking down and checking which branch each max came from.

The rerooting problem

The one-pass DP answers a question ABOUT one fixed root, or about each node's own subtree. But a whole family of problems asks something different: for EVERY node v, what is the answer when v is the root — that is, an answer that sees the entire tree from v's viewpoint, not just the part hanging below it. A clean example: for each node, find the sum of distances to all other nodes. The subtree DP only sees downward; from any node, most of the tree lies upward, through its parent. You need the part of the answer that comes from 'everything except my subtree' too.

The brute-force fix is to rerun the whole O(n) DP once per choice of root — n times, for O(n^2) total. That is fine for a few thousand nodes but quietly hopeless beyond that. The rerooting technique (sometimes 'rerooting DP' or the 'in-and-out' technique) gets every node's whole-tree answer in O(n) total with a second DFS. The key insight: when you move the root from a node v to an adjacent node c, almost everything stays the same. Only the relationship across the single edge v-c flips. So you should be able to update the answer in O(1) per edge as you 'slide' the root around, rather than rebuild from scratch.

How the second pass works

Concretely, for the sum-of-distances problem, the first pass computes, for each node v, the size of its subtree cnt[v] and down[v] = the sum of distances from v down to the nodes inside its subtree. Both follow simple post-order recurrences. The total answer at the chosen root is then exactly down[root]. The whole challenge is converting that single root's answer into every node's answer cheaply, and that is where the slide-the-root identity earns its keep.

Here is the move at the heart of it. Suppose ans[v] is the sum of distances from v to ALL nodes, and we already know ans[parent]. When we shift the root from the parent to its child v across that one edge, every node inside v's subtree gets one step CLOSER to v (there are cnt[v] of them), and every node OUTSIDE v's subtree gets one step FARTHER (there are n - cnt[v] of them). So ans[v] = ans[parent] - cnt[v] + (n - cnt[v]). That single O(1) update, applied as a second DFS pushes the root outward from the original root to each child in turn, fills ans for the whole tree.

Two passes, each O(n), so O(n) total — the same linear cost as the single-root DP, now delivering all n answers. That is the rerooting technique in full: a bottom-up pass to summarize each subtree, then a top-down pass that reuses a parent's complete answer to derive each child's, by reasoning only about the one edge that changes. The same skeleton handles many quantities — counts, maxima, products under a modulus, longest paths — as long as you can express 'remove this child's contribution and add the rest' as a cheap, reversible operation.

An honest catch on that 'reversible' word is worth pausing on. The distance update worked because subtracting a child's contribution is trivial — you just recompute from counts. But if the combine step is a max over children, you cannot simply 'subtract' the child you are rerooting through: the max might have BEEN that child. The standard fix is to precompute, at each node, enough information to answer 'best over all children except this one' — often a prefix-and-suffix max, or simply the top two values. Rerooting is genuinely linear, but only when the per-edge update is O(1); a careless combine can sneak an extra factor of the branching back in.

Limits, pitfalls, and honest scope

Keep the boundaries clear. Everything here rests on the tree being a tree — connected and acyclic. Add even one extra edge and you have a cycle, the clean parent-child partial order collapses, and a node's subtree can reach back up to influence its own ancestors. DP on general graphs is a much harder game; the gentle linearity of tree DP is exactly a dividend of having no cycles. If your input is 'a graph that happens to be a tree,' confirm it really is one (n nodes, n-1 edges, connected) before trusting any of this.

Two practical traps deserve naming. First, recursion depth: a tree can be a single long chain of n nodes, so a recursive DFS can recurse n deep and overflow the call stack on large inputs — the same real-machine cost the memoization guide warned about, and a reason to consider an explicit stack or an iterative post-order on very large trees. Second, the O(1)-per-edge promise is a promise about the COMBINE operation, not a law; if computing 'all children but one' or the rerooting update secretly costs O(degree) or O(log n), your total is no longer linear. Always check that the per-edge work really is constant before claiming O(n).

Finally, scope honestly. Rerooting buys you 'the answer at every node' for the price of one extra pass — a genuine asymptotic win over rerunning the DP n times. But if you only ever need the answer at one fixed root, the first pass alone suffices and the second pass is wasted effort; rerooting is not a free upgrade you always apply. As ever in this rung, the skill is recognizing the SHAPE of the question — one root or all roots, downward-only or whole-tree — and reaching for the matching tool. The next guide carries the same 'small reusable state, careful transition' instinct into a very different arena: subsets encoded as bitmasks.