| Safe Haskell | None |
|---|---|
| Language | Haskell2010 |
RerootFold
Description
Tree reroot fold
Folds of a tree with every node as root. Known as "tree rerooting DP", among other names.
Recall that Data.Tree has foldTree :: (a -> [c] -> c) -> Tree a -> c. foldReroot is similar but requires (b -> c -> b) and b to perform strict folds over [c].
g :: b -> c -> b must be commutative, in the sense that
(b g c1) g c2 = (b g c2) g c1
Sources:
- pajenegod, "The Ultimate Reroot Template" https://codeforces.com/blog/entry/124286
Synopsis
- foldReroot :: (a -> b -> c) -> (b -> c -> b) -> b -> Tree a -> Tree (a, c)
Documentation
foldReroot :: (a -> b -> c) -> (b -> c -> b) -> b -> Tree a -> Tree (a, c) Source #
Returns the same tree with each vertex accompanied by the fold of the tree if that vertex is made the root of the tree. f is called O(n) times. g is called O(n log n) times.