In hierarchical graph algorithms, trees provide a unique structural invariant: acyclic topology with exactly N - 1 edges connecting N vertices. Tree Dynamic Programming exploits this optimal substructure by decomposing trees into independent subtrees. The Subtree Rerooting Technique elevates this paradigm, converting quadratic O(N^2) all-roots queries into elegant, linear-time O(N) two-pass traversals.
1. Bottom-Up Subtree Dynamic Programming Foundations
In standard subtree DP, an arbitrary node (typically vertex 0 or 1) is designated as the root. Tree edges implicitly acquire parent-child directions. For any node u, its subproblem is defined exclusively over the subtree rooted at u:
- Leaf Nodes (Base Cases): Nodes with no children initialize base metrics (e.g.,
subtree_size[leaf] = 1,max_depth[leaf] = 0). - Internal Nodes (Post-Order Aggregation): In a post-order depth-first search (DFS), node
uvisits all childrenv ∈ children(u)before computing its own state by aggregating child metrics.
down_dist[u] = ∑_{v ∈ children(u)} (down_dist[v] + subtree_size[v])
This bottom-up pass resolves tree metrics relative to the initial root in O(N) time. However, if a problem requires answering the same query for every possible node as the root, running this DFS N times degrades performance to O(N^2).
2. The Rerooting Technique: Two-Pass Up-and-Down DP
The Rerooting Technique observes that when the root shifts across an edge from vertex u to adjacent vertex v, the entire tree structure does not scramble randomly. Only the parent-child relationship between u and v reverses:
Root Transfer Geometry across Edge (u, v)
When moving the root from u to v:
- All nodes inside
subtree(v)move 1 step closer to the new rootv. - All remaining
N - subtree_size[v]nodes outsidesubtree(v)move 1 step farther from the new rootv.
This gives rise to the classic constant-time rerooting transition equation:
By performing a second, pre-order DFS starting from the root and pushing updated states down to children, every vertex calculates its global all-nodes sum in O(1) time, achieving O(N) overall complexity.
3. C++ Implementation: All-Nodes Distance Summation
class TreeRerooting {
int n;
vector<vector<int>> adj;
vector<int> count;
vector<long long> ans;
void dfs1(int u, int p) {
count[u] = 1;
for (int v : adj[u]) {
if (v == p) continue;
dfs1(v, u);
count[u] += count[v];
ans[u] += ans[v] + count[v];
}
}
void dfs2(int u, int p) {
for (int v : adj[u]) {
if (v == p) continue;
// Reroot u -> v in O(1)
ans[v] = ans[u] - count[v] + (n - count[v]);
dfs2(v, u);
}
}
public:
vector<long long> sumOfDistancesInTree(int N, const vector<vector<int>>& edges) {
n = N;
adj.assign(n, {});
count.assign(n, 0);
ans.assign(n, 0);
for (const auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
dfs1(0, -1);
dfs2(0, -1);
return ans;
}
};
4. Handling Non-Invertible Aggregations (Top-2 Maximization)
When the aggregation operator is invertible (like addition or XOR), rerooting can simply subtract the child contribution. However, when operators are non-invertible (such as max() in tree diameter or maximum branch paths), subtraction is undefined.
To resolve non-invertible rerooting in O(N) time:
Top-2 Tracking
For each node u, track its top two longest child branches: best1 and best2, along with the child v_max that achieved best1. When pushing upward to v: if v == v_max, pass best2; otherwise pass best1.
Prefix & Suffix Sweeps
Construct prefix and suffix aggregation arrays over the child list of u. The exclusion of child v at index k is computed in O(1) by merging prefix[k - 1] and suffix[k + 1].
5. Algorithmic Complexity Comparison Matrix
6. Cache-Conscious Memory Layouts & Flattened Euler Tours
Standard tree traversals using linked node pointers or vector<vector<int>> adjacency lists suffer from severe hardware memory fragmentation. In competitive benchmarks and low-latency graph engines, traversing indirect pointers triggers repeated L1 and L2 cache misses.
To achieve hardware-optimal performance, trees can be flattened into a contiguous Euler Tour Array. By recording the entry time tin[u] and exit time tout[u] during the initial post-order traversal, every subtree rooted at u maps directly to a contiguous subarray [tin[u], tout[u]]. This enables vectorized SIMD memory loads, prefetching, and transforms subtree aggregations into simple contiguous range queries.
7. Centroid Decomposition vs. Subtree Rerooting: Decision Paradigm
When designing algorithms for tree-structured networks, choosing between Subtree Rerooting and Centroid Decomposition depends on query topology:
- Subtree Rerooting (O(N) Time): Optimal when you must calculate an all-nodes global metric for every vertex acting as the root, where subproblem transitions across adjacent edges are invertible or maintainable via prefix/suffix structures.
- Centroid Decomposition (O(N log N) Time): Mandatory when answering path queries between arbitrary pairs of vertices (such as counting pairs of nodes with distance equal to
K), or when transitions across tree boundaries cannot be expressed via local edge rotations.
8. Key Engineering Invariants & Numerical Limits
- Recursion Depth & Stack Overflow: In pathological skewed trees (such as degenerate line graphs where
N ∼ 2 × 10^5), default stack memory limits (8MB on Linux) will trigger fatal segmentation faults. In production services and judge environments, expand the call stack viasys.setrecursionlimit()or convert DFS routines into iterative post-order traversals using dual explicit stacks. - 64-bit Integer Overflow: Distance summations over unweighted or weighted trees of size
N = 10^5can reachN × N ∼ 10^{10}, quickly overflowing 32-bit signed integers. Always declare distance and aggregation vectors withlong longin C++ orint64in Go.