Course contentsShow
← Computer Science
Lesson 947 of 2,87222. Dynamic ProgrammingFree lesson

Rerooting Technique

Computing answers for all nodes as roots by transforming DP results from one root to adjacent roots.

Rerooting Technique

What you'll learn: How to efficiently compute tree DP answers for all nodes as the root by reusing computations instead of recalculating from scratch.


The Core Problem

You've learned how to run Tree DP from a single root—computing properties like subtree sizes, maximum independent sets, or diameter contributions. But what if the problem asks: "Compute the answer for each node as if it were the root"?

The naive approach would be to run Tree DP once for each of the N nodes, giving O(N²) time. Rerooting lets you do it in O(N) total.


How Rerooting Works

Think of it like rotating a mobile hanging from the ceiling:

  1. First Pass (Root → Leaves): Pick any node as the initial root and compute standard Tree DP values for all subtrees (just like before).

  2. Second Pass (Root → Leaves, with propagation): Now "shift" the root conceptually to each child. When you move the root from parent p to child c, you need to:

    • Remove c's contribution from p's answer (since c is now the root, not a subtree)
    • Add the "rest of the tree" (the part that was above p) as a new subtree under c

You're transforming answers by adjusting what counts as "subtree" versus "rest of tree."


Why It Works

Because trees have no cycles, each edge connects exactly two subtrees. By carefully updating DP values as you traverse edges in both directions, you reuse almost all computation—just tweaking boundaries.


Key Takeaway:
Rerooting transforms O(N²) "DP from every node" into O(N) by propagating adjusted DP results from one root to its neighbors in a second tree traversal.