Rerooting DP
Compute a tree answer for every possible root by combining one downward DP pass with one upward transfer pass.
Rerooting DP
The main note is rendered from the TeX source. Code lives in a separate C++ file so the write-up stays readable.
Overview
Rerooting DP is the pattern for ``compute the tree answer for every possible root.'' The technique is not about a particular formula. It is about splitting the answer at each node into:
what comes from its children,
what comes from the rest of the tree.
Problem-Driven Motivation
Many tree problems are easy for one fixed root and hard for all roots. A naive approach recomputes the whole DP \(n\) times, which turns an \(O(n)\) tree DP into \(O(n^2)\).
The optimization comes from noticing that moving the root across one edge only changes the answer locally. If that local change can be described by a transition formula, then all-root answers become a two-pass DP instead of \(n\) separate DFS runs.
Recognition Pattern
Rerooting is usually the right tool when:
the answer is required for every vertex,
the one-root version is already a standard tree DP,
a child's answer should be derivable from the parent's answer by removing one contribution and adding another.
Strong signals are:
sum of distances from every node,
best root under some subtree-merge score,
``solve for all roots'' wording in editorial discussions.
Derivation
The usual derivation has two phases.
Downward phase.
Compute a standard subtree DP:
subtree sizes,
subtree sums,
or any child-merge information needed by the final answer.
Upward / reroot phase.
Now imagine moving the root from parent \(v\) to child \(to\). If we can express the new answer at \(to\) using the old answer at \(v\), then one DFS over edges propagates all answers.
This is the key conceptual move:
The child needs the contribution of ``everything except its own subtree.''
For more complex merges, that contribution is often built with prefix/suffix aggregates over the children.
Worked Problem
Problem.
For every node \(v\), compute the sum of distances from \(v\) to all other nodes.
Step 1: subtree pass.
For each node \(v\):
\(\texttt{sub\_size[v]}\) = number of nodes in its subtree,
\(\texttt{down[v]}\) = sum of distances from \(v\) to all nodes in its subtree.
Step 2: root answer.
At the initial root, \(\texttt{answer[root]} = down[root]\).
Step 3: reroot across one edge.
If \(to\) is a child of \(v\), moving the root from \(v\) to \(to\):
decreases distance to each node in \(to\)'s subtree by \(1\),
increases distance to every other node by \(1\).
Therefore \[ answer[to] = answer[v] - sub\_size[to] + (n - sub\_size[to]). \]
Why this is enough.
That formula gives each child's full-tree answer from its parent's full-tree answer in \(O(1)\), so one second DFS propagates everything.
Implementation Reasoning
The important implementation question is not ``how do I run two DFS passes?'' It is ``what state is strong enough to transfer?''
For the sum-of-distances problem:
\(\texttt{sub\_size}\) is needed because rerooting changes distances for an entire subtree at once,
\(\texttt{down}\) gives the base answer at the initial root,
\(\texttt{answer}\) stores the full result after rerooting.
The code keeps the example intentionally direct because this is the cleanest rerooting entry point.
Correctness Intuition
The first DFS is ordinary tree DP. The second DFS is correct because every node in the tree is either inside the moved child's subtree or outside it, and those are exactly the two distance-change cases captured by the reroot formula.
Complexity Analysis
If each edge transfer is \(O(1)\), rerooting runs in \(O(n)\) total time and \(O(n)\) memory.
Common Pitfalls
Designing a state that is enough for one root but too weak to transfer to children.
Double-counting the child's own contribution when sending parent-side information downward.
Recomputing sibling merges from scratch instead of deriving them algebraically or with prefix/suffix arrays.
Variants and Failure Modes
Prefix-suffix rerooting handles child merges where one child needs ``all other children combined.''
Maximum/minimum-distance style rerooting often uses top-two child contributions.
If the answer is not transferable across one edge by a small state, rerooting may be the wrong abstraction.
Practice Problems
Sum of distances from every node.
Best root under a subtree-based score.
Generic ``all roots'' tree DP problems.
References
Code
Contest-ready reference implementation for the idea explained above.
#include <bits/stdc++.h>
using namespace std;
struct SumDistancesRerooting {
int n;
vector<vector<int>> tree;
vector<int> sub_size;
vector<long long> down;
vector<long long> answer;
explicit SumDistancesRerooting(int n)
: n(n), tree(n), sub_size(n, 1), down(n, 0), answer(n, 0) {}
void add_edge(int u, int v) {
tree[u].push_back(v);
tree[v].push_back(u);
}
void dfs_down(int v, int parent = -1) {
for (int to : tree[v]) {
if (to == parent) continue;
dfs_down(to, v);
sub_size[v] += sub_size[to];
down[v] += down[to] + sub_size[to];
}
}
void dfs_up(int v, int parent = -1) {
for (int to : tree[v]) {
if (to == parent) continue;
answer[to] = answer[v] - sub_size[to] + (n - sub_size[to]);
dfs_up(to, v);
}
}
vector<long long> solve(int root = 0) {
dfs_down(root);
answer[root] = down[root];
dfs_up(root);
return answer;
}
};
// Example application: compute sum of distances from every node.
vector<long long> sum_of_distances_on_tree(int n, const vector<pair<int, int>>& edges) {
SumDistancesRerooting solver(n);
for (const auto& edge : edges) solver.add_edge(edge.first, edge.second);
return solver.solve(0);
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.