V

Algorithm Visualizer

ZHEN
Share on WeiboShare on XGitHub repositoryAuthor website
Learning ToolsAlgorithm Complexity ReferenceAlgorithm Learning Paths
Data StructuresArrayLinked ListStackQueue and DequeBinary Search TreeBinary HeapHash TableGraphTrieDisjoint Set UnionLRU CacheSkip ListSegment TreeB+ TreeBloom FilterFenwick Tree
SortingBubble SortCocktail Shaker SortBitonic SortSelection SortInsertion SortBinary Insertion SortShell SortMerge SortTop-Down Merge SortQuick SortThree-Way Quick SortDual-Pivot Quick SortHeap SortCounting SortRadix SortBucket Sort
Graph AlgorithmsDijkstra's Shortest PathKruskal's Minimum Spanning TreePrim's Minimum Spanning TreeBellman-Ford Shortest PathsTopological SortFloyd-WarshallStrongly Connected Components2-SATMaximum FlowBipartite MatchingLowest Common AncestorEulerian Path
Dynamic ProgrammingEdit Distance0/1 KnapsackUnbounded KnapsackLongest Common SubsequenceLongest Increasing SubsequenceCoin ChangeStone MergingTraveling Salesperson DPTree Dynamic ProgrammingDigit DPRerooting DP
Backtracking and SearchN-QueensSubsetsPermutationsCombination SumMaze Solving with DFSNumber of IslandsWord SearchSudoku SolverA* Search
StringsKMP String MatchingRabin-Karp String MatchingBoyer-Moore String MatchingManacher's Longest Palindromic SubstringSuffix ArrayLCP ArrayAho-Corasick AutomatonZ Function
Math and Number TheorySieve of EratosthenesLinear SieveEuclidean AlgorithmBinary ExponentiationExtended Euclidean AlgorithmChinese Remainder TheoremEuler's Totient FunctionMiller-Rabin Primality TestFast Fourier TransformPollard's Rho Factorization
Computational GeometryConvex HullRotating CalipersClosest Pair of PointsLine Segment IntersectionBentley-Ottmann Sweep Line
SearchingBinary SearchLower and Upper BoundSearch in a Rotated Sorted ArrayBinary Search on the AnswerTernary Search

Rerooting DP

Compute subtree answers bottom-up, then transfer the whole-tree answer across every edge in a second pass.

Core idea

A postorder pass solves each subtree for one arbitrary root. A preorder pass then moves the root across every edge using a constant-time relation between parent and child answers.

Read the visualization

The first columns accumulate subtree sizes and downward distances. The answer column begins at the original root and spreads outward with the reroot formula.

sizedownans
0· root
1·L
2·R
3·LL
4·LR

Root the tree once and prepare subtree sizes plus downward distance sums.

1function sumOfDistances(n: number, adj: number[][]): number[] {
2 const size = new Array(n).fill(1);
3 const down = new Array(n).fill(0);
4 const ans = new Array(n).fill(0);
5 const dfs1 = (u: number, p: number): void => { // number one init: postorder
6 for (const v of adj[u]) if (v !== p) {
7 dfs1(v, u);
8 size[u] += size[v];
9 down[u] += down[v] + size[v]; // child subtree down 1 step
10 }
11 };
12 const dfs2 = (u: number, p: number): void => { // number reroot: reroot root
13 for (const v of adj[u]) if (v !== p) {
14 ans[v] = ans[u] - size[v] + (n - size[v]); // reroot size[v] reroot n−size[v]
15 dfs2(v, u);
16 }
17 };
18 dfs1(0, -1);
19 ans[0] = down[0]; // number one root: root root answer
20 dfs2(0, -1);
21 return ans;
22}
tree0 root; 1,2 as child; 3,4 as 1 child
targetans[u] = Σ dist(u, ·), all 5 count
1 / 12

Complexity and tradeoffs

Time: O(n). Space: O(n). A local reroot transition turns one rooted result into answers for every possible root.

Invariant: When processing edge parent to child, the parent's whole-tree answer and the child's subtree summary are already complete.

Where it fits

Rerooting computes all-root distance sums, eccentricity-style values, and tree contributions in linear time instead of repeating a traversal from every node.