Algorithms / Tree Dp Rerooting
Least You Need to Know: Tree DP, Child-State Combination, and Rerooting Intuition
Tree dynamic programming works because each node can summarize its subtree from its children. Rerooting extends that idea by reusing previously computed information when the root perspective shifts from one node to another.
The least you need to know
- A rooted tree separates each node into independent child subproblems.
- Bottom-up tree DP combines child summaries into a parent summary.
- Rerooting passes information from parent context into each child.
- The rerooting trick avoids recomputing a full DP from every possible root.
- Choosing the right state is more important than memorizing formulas.
Key notation
dp_down[u]
summary computed from the subtree of `u`
dp_up[u]
summary contributed from outside the subtree of `u`
reroot
transfer root perspective across an edge
Tiny worked example
- Suppose `dp_down[u]` stores the longest downward path starting at `u`.
- Combine child answers to compute the parent answer.
- For all-roots answers, also send each child the best information coming from the parent side.
- That reuse is rerooting: one global sweep down, one sweep back up, instead of starting over from each node.
Common mistakes
- Students often mix subtree-only answers with all-roots answers.
- Rerooting needs a way to exclude the current child when building the child's parent-side value.
- Tree DP state should summarize exactly what the parent needs, not every local detail.
How to recognize this kind of problem
- Each child subtree contributes independently to a node answer.
- The same quantity is requested for every possible root.
- A naive `O(n^2)` recomputation from each root feels too slow.