Rerooting Technique

Some problems ask: for each node, what's the answer if that node were the root? Naive approach: run tree DP $n$ times, once per root. That's $O(n^2)$. Rerooting does it in $O(n)$ using two passes.

First, compute answers with an arbitrary root. Then, "move" the root to each neighbor efficiently by adjusting the dp values. When does root choice matter? If $dp[\text{node}]$ depends on the direction of parent-child relationships, different roots give different answers.