Tree Dynamic Programming & Subtree Rerooting: Linear-Time All-Nodes Aggregations

Tree graphs possess unique topological properties: acyclicity, unique simple paths between any node pair, and natural inductive subproblems. Tree DP exploits this hierarchy via post-order and pre-order DFS traversals.

1. Post-Order Bottom-Up Aggregation

In standard Tree DP, we root the tree arbitrarily at node 0 and compute subtree answers from leaves upward:

void dfs(int u, int parent) {
    dp[u] = 1; // Base case: node itself
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs(v, u);
        dp[u] += dp[v];
    }
}

2. The 2-Pass Subtree Rerooting Technique

To compute answers for every node as if it were the tree root without recomputing in $O(N^2)$, the Rerooting Technique uses two passes:

1. Pass 1 (Bottom-Up DFS): Compute subtree aggregates for root 0.
2. Pass 2 (Top-Down DFS): Transfer the root from parent $u$ to child $v$ in $O(1)$ time:

   dp[v] = dp[u] - count[v] + (N - count[v]);