Dynamic Programming • Trees

Rerooting DP

An advanced tree DP technique to compute an answer for ALL nodes acting as the root in O(N) time, rather than the naive O(N²).

Try Interactive Simulator

Overview

If you need to find something like "Sum of Distances to all nodes" for EVERY node in a tree, running a DFS from every node takes O(N²). Rerooting DP does it in O(N).

Phase 1: Precompute

Run a standard post-order DFS starting from an arbitrary root (e.g., node 0). Calculate the answer just for this root, and also compute auxiliary data like subtree sizes.

Phase 2: Shift Root

Run a second, pre-order DFS. When you move the root from node `u` down to its child `v`, you don't recompute from scratch. You just adjust `u`'s answer based on the shift.

The Adjustment

When shifting root to `v`, all nodes in `v`'s subtree get 1 step closer (subtract `count[v]`). All other nodes in the tree get 1 step further (add `N - count[v]`).

0

1

2

Code Tracker

:::

1// Phase 1: Post-order DFS

2function dfs1(u, p) {

3 for (let v of adj[u]) {

4 if (v === p) continue;

5 dfs1(v, u);

6 count[u] += count[v];

7 ans[u] += ans[v] + count[v];

8 }

9}

10// Phase 2: Pre-order DFS (Rerooting)

11function dfs2(u, p) {

12 for (let v of adj[u]) {

13 if (v === p) continue;

14 // Shift root from u to v

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

16 dfs2(v, u);

17 }

18}

Rerooting Dp

Rerooting Dp

Rerooting DP

Overview

Phase 1: Precompute

Phase 2: Shift Root

The Adjustment

Rerooting DP

Overview

Phase 1: Precompute

Phase 2: Shift Root

The Adjustment