| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Data.Graph.Tree.Lca
Description
Lowest common ancestor and tree path folding via LCA (binary lifting).
Warning
The current lca is really slow. TODO: Fix it to be \(\log N\).
Synopsis
- type LcaCache a = (Vector Int, IndexMapWithAction a, Vector (IndexMapWithAction a))
- lca :: (HasCallStack, Unbox a) => LcaCache a -> Vertex -> Vertex -> (Vertex, Int)
- lcaLen :: (HasCallStack, Unbox a) => LcaCache a -> Int -> Int -> Int
- foldPathViaLca :: forall a. (HasCallStack, Unbox a, Semigroup a) => LcaCache a -> (Vertex, a) -> (Vertex, a) -> a
Documentation
type LcaCache a = (Vector Int, IndexMapWithAction a, Vector (IndexMapWithAction a)) #
`(parents, depths, parents')`
lca :: (HasCallStack, Unbox a) => LcaCache a -> Vertex -> Vertex -> (Vertex, Int) #
\(O(\log^2 N)\) Returns the lowest common ancestor `(v, d)` with the help of the binary lifting technique. REMARK: Use 0-based index for the graph vertices.
lcaLen :: (HasCallStack, Unbox a) => LcaCache a -> Int -> Int -> Int #
\(O(\log^2 N)\) Retrieves the length between given two vertices with the help of LCA.
foldPathViaLca :: forall a. (HasCallStack, Unbox a, Semigroup a) => LcaCache a -> (Vertex, a) -> (Vertex, a) -> a #
\(O(\log^2 N + \mathit{sact} \cdot \mathit{popCount}(V)))\) Calculates the folding value of the path between two vertices in a tree.
Typical problems
- ABC 235 E - MST + 1 In this problems we have self-looping edge though.