8.11 Rerooting Dynamic Programming
Many tree algorithms compute information relative to a fixed root.
8.11 Rerooting Dynamic Programming
Many tree algorithms compute information relative to a fixed root. Subtree size, subtree sum, height, and many dynamic programming states naturally flow upward from descendants toward the root.
However, some problems ask a different question:
What would the answer be if every node were the root?
At first, this appears expensive. If a tree contains n nodes, recomputing a complete DFS from every possible root leads to O(n²) complexity.
Rerooting Dynamic Programming avoids this cost. It computes answers for all possible roots in linear time by carefully reusing information from neighboring nodes.
This technique is one of the most powerful patterns in tree algorithms. Many seemingly difficult problems collapse into a pair of DFS traversals once rerooting is understood.
Problem
You need to compute a value for every possible root of a tree.
Examples include:
- Sum of distances to all nodes
- Maximum distance to any node
- Number of reachable configurations
- Tree DP values under different roots
- Cost of serving a network from each node
Running a full traversal for every root is too expensive.
Solution
Compute information in two passes.
The first pass gathers information from descendants.
The second pass propagates information from ancestors.
Consider this tree:
0
/ \\n 1 2
/ \\n 3 4
Suppose we want:
sum of distances
from every node
to all other nodes
A brute-force solution performs a traversal from every node.
Instead, use rerooting.
First DFS
Compute:
- subtree sizes
- distance sums inside each subtree
package main
func dfs1(
tree [][]int,
node int,
parent int,
size []int,
dp []int,
) {
size[node] = 1
for _, next := range tree[node] {
if next == parent {
continue
}
dfs1(
tree,
next,
node,
size,
dp,
)
size[node] += size[next]
dp[node] += dp[next] + size[next]
}
}
After this traversal:
dp[node]
contains information about descendants.
Second DFS
Propagate information outward.
func dfs2(
tree [][]int,
node int,
parent int,
n int,
answer []int,
size []int,
) {
for _, next := range tree[node] {
if next == parent {
continue
}
answer[next] =
answer[node] +
n -
2*size[next]
dfs2(
tree,
next,
node,
n,
answer,
size,
)
}
}
The result:
answer[node]
contains the final value for every possible root.
Total complexity:
O(n)
Discussion
The key insight is that neighboring roots differ only slightly.
Suppose:
A
|
B
If the tree is rooted at A, every node in B's subtree is one edge farther from A.
When the root moves from A to B:
- nodes inside
B's subtree become one step closer - all other nodes become one step farther
Nothing else changes.
Rerooting exploits this observation.
Instead of recomputing everything, update the answer incrementally.
Understanding the Distance Formula
Suppose:
answer[node]
already stores:
sum of distances
from node
to every vertex
Move the root from:
node
to:
child
Every node in the child's subtree becomes:
1 closer
There are:
size[child]
such nodes.
Contribution:
-size[child]
Every other node becomes:
1 farther
There are:
n - size[child]
such nodes.
Contribution:
+(n - size[child])
Combining both:
answer[child]
=
answer[node]
+
n
-
2×size[child]
This single equation eliminates an entire traversal.
A Simpler Example
Suppose we want:
subtree size
for every root
At first glance, rerooting seems unnecessary.
Every root sees:
n
nodes.
The answer is trivial.
This example illustrates an important principle:
Rerooting is useful only when the answer changes with the root.
Many tree properties remain invariant.
Many others change dramatically.
Understanding the difference is often the hardest part of designing the algorithm.
Tree DP States
Rerooting becomes more interesting when the DP state contains more information.
Suppose:
dp[node]
stores:
maximum path length
inside subtree(node)
When moving the root, information from ancestors suddenly becomes relevant.
The second DFS carries this information downward.
A common pattern looks like:
Pass 1:
child → parent
Pass 2:
parent → child
The first pass computes local information.
The second pass injects global information.
Together they provide complete answers.
Viewing Rerooting as Message Passing
An intuitive way to think about rerooting is message passing.
Every subtree sends a summary upward.
Examples:
size
sum
maximum
DP state
The root combines these summaries.
Then the root sends information back downward.
Each child receives:
everything except itself
This allows the child to compute the answer as if it were the root.
Many rerooting implementations become easier once viewed as information exchange between parent and child.
Generic Rerooting Framework
Many problems follow the same structure.
Step 1
Compute a subtree state.
func dfs1(...)
Examples:
size
sum
maximum
count
probability
Step 2
Compute a transition.
Parent state
→
Child state
This is the rerooting formula.
Step 3
Propagate answers.
func dfs2(...)
The first traversal aggregates.
The second traversal redistributes.
The details vary, but the structure remains remarkably consistent.
Example: Maximum Distance from Every Node
Suppose we need:
For each node,
distance to the farthest node.
A naive solution:
Run BFS from every node.
Complexity:
O(n²)
A rerooting solution computes:
best downward path
during the first DFS.
Then computes:
best path through parent
during the second DFS.
Final complexity:
O(n)
This optimization appears frequently in tree-based optimization problems.
Example: Counting Colored Nodes
Suppose every node is:
red
or
blue
We need:
Number of red nodes
outside each subtree.
The first DFS computes:
red nodes inside subtree
The second DFS computes:
red nodes outside subtree
Together:
inside + outside
gives global information for every node.
The pattern is identical to distance rerooting.
Only the state changes.
Rerooting and Dynamic Programming
Rerooting is often introduced as a specialized technique.
A more useful perspective is:
Rerooting is dynamic programming on edges.
The algorithm answers:
What changes when
the root crosses
this edge?
Each transition updates the state using information already computed.
This is precisely the same idea used in many DP algorithms.
The only difference is that the state lives on a tree.
Complexity Analysis
Let:
n= number of nodes
First traversal:
| Operation | Complexity |
|---|---|
| DFS aggregation | O(n) |
Second traversal:
| Operation | Complexity |
|---|---|
| DFS propagation | O(n) |
Total:
| Operation | Complexity |
|---|---|
| Complete rerooting DP | O(n) |
Memory:
| Structure | Complexity |
|---|---|
| DP arrays | O(n) |
| Recursion stack | O(h) |
where h is tree height.
This is dramatically better than recomputing from every root.
Common Mistakes
A common mistake is attempting to recompute child states during the second traversal.
The first DFS already computed them.
The second DFS should reuse existing information.
Another mistake is forgetting that the child needs information from:
entire tree
minus child subtree
Many incorrect implementations pass only the parent's local state.
The missing information causes subtle errors.
A third mistake is designing the wrong DP state.
Rerooting succeeds when the state can be updated efficiently while moving across an edge.
If the state cannot be transformed incrementally, rerooting may not be the right approach.
Finally, many implementations become difficult to understand because they combine both DFS passes into one function. Keeping aggregation and propagation separate usually produces clearer code.
Takeaway
Rerooting Dynamic Programming computes answers for every possible root without repeating work. The technique relies on two traversals: one that aggregates information from descendants and another that propagates information from ancestors. The crucial insight is that moving the root across an edge changes only a small portion of the state. By exploiting that fact, rerooting transforms many quadratic tree algorithms into linear-time solutions and provides a powerful framework for global tree analysis.