Freaks City

Re-rooting DP is a tree-DP variant that looks intimidating at first, yet becomes very mechenical once the pattern is recognized. The following problems illustrate the key techniques. Problem 1 – USACO 2012 FEB "Nearby Cows" Task: for every node i compute the sum of weights of all nodes whose distance to i is at most K. Constraints: n ...

The elimination rule—removing consecutive identical elements when their count reaches a threshold $k$—suggests an interval dynamic programming approach. A two-dimensional DP state is insufficient because it cannot capture how the leftmost element in a segment is eventually removed. To resolve this, we introduce a third dimension that tracks how ...