Sign in to watch this lesson
Advanced - Trees Ā· 5:32
Tree DP & Rerooting
A tree DP computes each vertex's value from its children's values in one sweep from the leaves, like subtree sizes or the sum of distances inside a subtree. Rerooting adds a second sweep from the root that hands every child a summary of the rest of the tree, so an answer for every possible root costs O(n) in total; for the sum of distances the rule is f(c) = f(p) + n - 2*sz[c]. When the combining operation cannot be undone, such as max, each child gets the best of its siblings from prefix and suffix maxima.
You will learn
- Write a subtree DP that computes values such as sizes and in-subtree distance sums from the children, leaves first
- Derive and apply the rerooting rule f(c) = f(p) + n - 2*sz[c] to get the sum of distances for every vertex in O(n)
- Pass 'the rest of the tree' to each child with prefix/suffix maxima (or the top two values) when the operation is not invertible
- Implement both passes iteratively over a BFS order and choose 64-bit or 128-bit sums from the size of the answer