The rerooting technique follows a two-phase pattern that turns brute force into .
Phase : Root the tree at any node (say node ). Run DFS to compute "downward" DP values for all nodes. Each dp_down[v] answers the question from 's perspective when looks down into its subtree.
Phase : Run another DFS to compute "upward" contributions. Each dp_up[v] captures what would see if it looked up toward the rest of the tree.
The Core idea is that when you reroot from parent to child , the subtree rooted at (excluding ) becomes part of 's upward view. You compute this contribution incrementally instead of re-running the entire DFS.
function reroot(tree)
dfs_down(1, -1) // Phase 1
dfs_up(1, -1, 0) // Phase 2
for each node v
answer[v] := combine(dp_down[v], dp_up[v])
Space complexity is for the data structures used.