Rerooting
← Back to On Trees
A technique for efficiently computing a tree DP answer for every possible root. After computing the answer for one root, results are propagated to adjacent nodes in O(1) each, giving O(n) total time for all roots instead of O(n^2).