Rerooting in Contests (Recognition)

Rerooting problems often say "for each node" or "for all possible roots" in the problem statement. That is your signal to think about rerooting. If brute force is $O(n^2)$ and constraints are $n \leq 100{,}000$ or $n \leq 200{,}000$, you need $O(n)$ or $O(n \log n)$. Rerooting gives you $O(n)$, which is often the intended solution.

After solving a few rerooting problems, you will see the pattern immediately. The hard part is setting up the DP state and combine function correctly, not the two-pass structure itself. That stays the same across all problems.

Space complexity is $O(n)$ for the data structures used.