Rerooting Template (General pattern)

The rerooting technique follows a two-phase pattern that turns $O(n^2)$ brute force into $O(n)$.

Phase $1$: Root the tree at any node (say node $1$). Run DFS to compute "downward" DP values for all nodes. Each dp_down[v] answers the question from $v$'s perspective when $v$ looks down into its subtree.

Phase $2$: Run another DFS to compute "upward" contributions. Each dp_up[v] captures what $v$ would see if it looked up toward the rest of the tree.

The Core idea is that when you reroot from parent $p$ to child $c$, the subtree rooted at $p$ (excluding $c$) becomes part of $c$'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 $O(n)$ for the data structures used.