tree
A tree rooted at root, owning its own fresh heavy-first preorder domain t.Pre.
Generated from spec/std/tree.cp by cpl doc --format json.
Rooted
pub struct Rooted<V, Pre>A tree rooted at root, owning its own fresh heavy-first preorder domain t.Pre.
Built in O(n) without recursion; memory is seven [V] arrays, one [Pre] array and child
lists.
Rooted.par
par: [V]?VThe parent; None at the root.
Rooted.far
far: [V]IntThe total edge length from the root; equal to the depth when the edges have no lengths.
Rooted.sz
sz: [V]1..=V.countThe number of vertices in the subtree.
Rooted.bfs
bfs: List<V>Breadth-first order: the children of v are bfs[k0[v]..k1[v]], so no vertex owns a list.
Rooted.heavy
heavy: [V]?VThe child with the largest subtree; None at a leaf.
Rooted.top
top: [V]VThe highest vertex of the heavy chain through v.
Rooted.at
at: [Pre]VThe inverse of tin / pos.
Rooted.new
fn new(next: Next<V>, root: V) -> Rooted<V, _>Roots the tree given by next at root: Rooted(g, root: r) for a Graph,
Rooted(lists, root: r) for a table of neighbour lists [V]List<V>, and
Rooted(root: r, next: u => ...) for anything else.
next may list every neighbour (the parent is skipped) or only the children, as vertices or
as arcs. The tree is the breadth-first spanning tree from root, children in the order next
lists them, so on a graph with extra edges depth is the distance from the root. Edge
lengths come from the arcs, as in every graph algorithm: Weighted arcs (a w field, or
g.weighted(f)) give dist, w and diameter their lengths; others count 1 per edge.
The heavy child of a vertex is the child with the largest subtree, the first in child order
on ties; t.Pre is the preorder that visits the heavy child first and then the other
children in child order.
- cost: O(n + m) for m listed arcs, without recursion
- traps: when some vertex is not reachable from
root
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.children(0).collect() == [1, 2] and t.children(1).collect() == [3, 4] and t.depth(4) == 2
Rooted.from_parents
fn from_parents(par: [V]?V) -> Rooted<V, _>Builds a rooted tree from parents keyed by vertex: par: [V]?V with None at the root, or
the usual input shape "parents of 2..n" read as read<[V.drop(1)]V>(), whose one missing key
is the root.
Several roots give a forest, as forest does, with the roots in key order. Children are in
increasing key order.
- cost: O(n)
- empty: a
parwith no root, empty or cyclic, traps - traps: when the parents have a cycle;
try_from_parentsis for input that may
Examples:
domain V = 0..3; let par: [V]?V = [None, Some(0), Some(1)]; let t = Rooted.from_parents(par); t.depth(2) == 2 and t.parent(1) == Some(0)
Rooted.try_from_parents
fn try_from_parents(par: [V]?V) -> ?Rooted<V, _>from_parents for parents that may not form a forest: None when they have a cycle.
let t = Rooted.try_from_parents(up) else: print("NO"); return- cost: O(n)
- empty:
Nonewhenparhas no root - traps: never
Examples:
domain V = 0..2; let par: [V]?V = [Some(1), Some(0)]; Rooted.try_from_parents(par) == None
Rooted.forest
fn forest(next: Next<V>, from: List<V>) -> Rooted<V, _>One tree per root: next must reach every vertex from exactly one of from.
Each tree is built as new builds it. The trees sit one after another in t.Pre, in the
order of from; t.root is the first root. Paths and lowest common ancestors exist only
within one tree (root_of tells).
- cost: O(n + m)
- empty:
frommust be nonempty - traps: when
fromis empty, or some vertex is reached from no root or from two
Examples:
domain V = 0..4; let adj: [V]List<V> = [[1], [0], [3], [2]]; let t = Rooted.forest(adj, from: [2, 0]); t.roots.collect() == [2, 0] and t.root_of(1) == 0
Rooted.build
fn build(next: Next<V>, roots: List<V>) -> Rooted<V, _>Rooted.roots
fn roots(self) -> yields VThe roots in the order given: one for new, one per tree for forest, key order for
from_parents.
- cost: O(1) to make, O(1) per root
- order: as given at construction
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.roots.collect() == [0]
Rooted.pos
fn pos(self, v: V) -> PreThe position of v in this tree's own preorder domain t.Pre; the inverse of at.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.at[t.pos(3)] == 3 and t.pos(1) < t.pos(3) and t.pos(4) < t.pos(2)
Rooted.parent
fn parent(self, v: V) -> ?VThe parent of v; None at a root.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.parent(3) == Some(1) and t.parent(0) == None
Rooted.up_arc
fn up_arc<A>(self, v: V) -> ?AThe arc v was entered by, with every field next gave it (t.up_arc(v)!.cost on a tree
read with a cost field); None at a root. Edge data stays on the arcs, so no [V] side
array is built from the edge list.
- cost: O(1)
- traps: never
Examples:
domain V = 0..3; let es: [0..2](u: V, v: V) = [(u: 0, v: 1), (u: 1, v: 2)]; let t = Rooted(Graph.undirected(es), root: 0); t.up_arc(2)!.to == 2 and t.up_arc(0) == None
Rooted.reorder
fn reorder<T>(self, a: [V]T) -> [Pre]TReorders a vertex-indexed array into preorder: out[t.pos(v)] == a[v], ready to build a
SegTree or Fenwick over t.Pre.
- cost: O(n)
- empty: never empty; a tree has a vertex
- order: by
t.Pre - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.reorder([10, 11, 12, 13, 14]).collect() == [10, 11, 13, 14, 12]
Rooted.children
fn children(self, v: V) -> yields VThe children of v, in the order next listed them. Children are stored contiguously, so
nothing is allocated.
- cost: O(1) to start, O(1) per child
- empty: nothing at a leaf
- order: as
nextlisted them - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.children(1).collect() == [3, 4] and t.children(2).count() == 0
Rooted.child_arcs
fn child_arcs<A>(self, v: V) -> yields AThe arcs from v down to its children, with every field next gave them
(for a in t.child_arcs(v): up(a.to) + a.w), so edge data needs no side array.
- cost: O(1) per child
- empty: nothing at a leaf
- order: child order
- traps: never
Examples:
domain V = 0..3; let es: [0..2](u: V, v: V) = [(u: 0, v: 1), (u: 1, v: 2)]; let t = Rooted(Graph.undirected(es), root: 0); t.child_arcs(1).map(a => a.to).collect() == [2]
Rooted.excl_fold
fn excl_fold<T, M>(self, v: V, op: M, f: V -> T) -> yields (c: V, rest: T)For each child c of v, in child order, the fold with op of f over v's other
children: the step of a rerooting DP, with no division or inverse.
The fold keeps child order (earlier siblings, then later ones), so op need not commute;
with one child, rest is the identity. Prefix and suffix folds make it O(k) for k
children.
for (c, rest) in t.excl_fold(v, mul, c => down[c] + 1):
up[c] = (up[v] * rest + 1) % m- cost: O(k) calls of
fand ofop, O(k) memory - empty: nothing at a leaf
- order: child order
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.excl_fold(0, add, c => t.size(c)).collect() == [(c: 1, rest: 1), (c: 2, rest: 3)]
Rooted.depth
fn depth(self, v: V) -> IntThe number of edges between v and its root.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.depth(0) == 0 and t.depth(4) == 2
Rooted.size
fn size(self, v: V) -> IntThe number of vertices in the subtree of v, v included.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.size(0) == 5 and t.size(1) == 3 and t.size(2) == 1
Rooted.light
fn light(self, v: V) -> yields VThe children of v other than its heavy child, in child order. Every vertex has O(log n)
light edges above it, which is what small-to-large merging pays for.
- cost: O(children)
- empty: nothing at a leaf
- order: child order
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.light(0).collect() == [2] and t.light(1).collect() == [4]
Rooted.root_of
fn root_of(self, v: V) -> VThe root of the tree that holds v: always t.root unless built as a forest.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.root_of(4) == 0
Rooted.subtree
fn subtree(self, v: V) -> yields VThe vertices of v's subtree in preorder, v first: t.at[p] for p in t.sub(v).
- cost: O(size(v))
- empty: never empty; it holds
v - order:
t.Preorder - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.subtree(1).collect() == [1, 3, 4] and t.subtree(0).collect() == [0, 1, 3, 4, 2]
Rooted.down
fn down<T>(self, init: T, f: (T, V) -> T) -> [V]TA top-down pass: out[v] = f(out[parent], v), and f(init, r) at a root r. The state on
the path from the root, such as a prefix maximum or a distance.
- cost: O(n) calls of
f - empty: never empty
- order: keyed by
V;fruns int.Preorder - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.down(0, (d, v) => d + 1) == [1, 2, 2, 3, 3]
Rooted.up
fn up<T, U, M>( self, op: M, lift: (T, V, V) -> U = (x, c, p) => x, finish: (U, V) -> T, ) -> [V]TA bottom-up tree DP: out[v] = finish(fold with op of lift(out[c], c, v) over children c, v).
lift sees both ends of the edge, child first, and defaults to the child's value. Children
fold in child order, so op need not commute; a leaf folds nothing and gets the identity.
- cost: O(n) calls of
lift,opandfinish - empty: never empty
- order: keyed by
V - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.up(add, finish: (s, v) => s + 1) == [5, 3, 1, 1, 1]
Rooted.reroot
fn reroot<T, U, M>( self, op: M, lift: (T, V, V) -> U = (x, c, p) => x, finish: (U, V) -> T, ) -> [V]TThe same DP as up, for every root at once: out[v] is what up would give at v if the
tree were rooted at v.
Each vertex folds its parent's side first, then its children in child order; the sibling
folds use prefixes and suffixes, so op needs no inverse.
- cost: O(n) calls of
liftandfinish, O(n) calls ofop - empty: never empty
- order: keyed by
V - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.reroot(add, lift: (x, c, p) => 1, finish: (s, v) => s) == [2, 3, 1, 1, 1]domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.reroot(add, finish: (s, v) => s + 1) == [5, 5, 5, 5, 5]
Rooted.shapes
fn shapes(self) -> (domain Shape, of: [V]Shape)The isomorphism class of every subtree: of[a] == of[b] exactly when the subtrees of a and
b are the same rooted tree up to reordering children.
Classes are numbered in reverse preorder (children before parents) by first appearance, so
a leaf, if any, has class Shape.first.
- cost: O(n log n)
- empty: never empty
- order:
ofkeyed byV - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let (domain S, of) = t.shapes(); of[3] == of[2] and of[1] != of[0] and S.count == 3
Rooted.subtree_sizes
fn subtree_sizes(self) -> [V]IntThe size of every subtree, by vertex: t.subtree_sizes[v] == t.size(v).
- cost: O(1); a view of the stored sizes
- empty: never empty
- order: keyed by
V - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.subtree_sizes == [5, 3, 1, 1, 1]
Rooted.centroid
fn centroid(self) -> VA centroid of the tree holding t.root: a vertex whose removal leaves no piece of more than
half its vertices. Found by walking heavy children down from the root while the heavy
child's subtree is more than half.
- cost: O(depth)
- ties: of two centroids, the one nearer the root
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.centroid() == 1
Rooted.centroids
fn centroids(self) -> List<V>Every centroid of the tree holding t.root, one or two. Two happen only when the number of
vertices is even and one edge splits the tree in halves.
- cost: O(depth)
- empty: never empty
- order: the one nearer the root first
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.centroids() == [1]domain P = 0..4; let adj: [P]List<P> = [[1], [0, 2], [1, 3], [2]]; Rooted(adj, root: 0).centroids() == [1, 2]
Rooted.tour
fn tour(self) -> yields Visit<V, V>The enter/exit Euler tour, the Visit events of std.graph.dfs: Enter(v, via:) when
entering v and Exit(v, via:) when leaving its subtree, via the parent (None at a
root, and a tree has no Again), children in t.Pre order, each tree of a forest
in turn. Iterative, so deep trees are safe.
- cost: O(1) to make, O(n) to walk
- empty: never empty
- order:
Enterevents int.Preorder;Exit(v, _)right after the last event ofv's subtree - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.tour.collect() == [Enter(0, None), Enter(1, Some(0)), Enter(3, Some(1)), Exit(3, Some(1)), Enter(4, Some(1)), Exit(4, Some(1)), Exit(1, Some(0)), Enter(2, Some(0)), Exit(2, Some(0)), Exit(0, None)]
Rooted.sub
fn sub(self, v: V) -> Range<Pre>The positions of v's subtree, v first: one contiguous range of t.Pre.
- cost: O(1)
- empty: never empty; it holds
t.pos(v) - order: increasing positions
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.sub(1).map(p => t.at[p]).collect() == [1, 3, 4]
Rooted.below
fn below(self, v: V) -> Range<Pre>The positions of v's descendants: sub(v) without v.
- cost: O(1)
- empty: empty at a leaf
- order: increasing positions
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.below(1).map(p => t.at[p]).collect() == [3, 4] and t.below(2).count() == 0
Rooted.is_anc
fn is_anc(self, a: V, b: V) -> BoolWhether a is an ancestor of b; a vertex is its own ancestor.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.is_anc(1, 3) and t.is_anc(3, 3) and not t.is_anc(2, 3)
Rooted.lower
fn lower(self, u: V, v: V) -> VThe child end of the tree edge between u and v, in either order.
- cost: O(1)
- ties: None; exactly one end is the child
- traps: when
uandvare not joined by a tree edge
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.lower(0, 1) == 1 and t.lower(3, 1) == 3
Rooted.lca
fn lca(self, a: V, b: V) -> VThe lowest common ancestor of a and b, by heavy-path climbing.
- cost: O(log n)
- traps: when
aandbare in different trees of a forest
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.lca(3, 4) == 1 and t.lca(3, 2) == 0 and t.lca(1, 3) == 1
Rooted.dist
fn dist(self, a: V, b: V) -> IntThe length of the path between a and b: its number of edges, or the total of its edge
lengths in a tree built from Weighted arcs.
- cost: O(log n)
- traps: when
aandbare in different trees of a forest
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.dist(3, 2) == 3 and t.dist(4, 4) == 0
Rooted.path
fn path(self, a: V, b: V) -> List<V>The simple path of vertices from a to b, both included.
- cost: O(log n + |path|)
- empty: never empty;
[a]whena == b - order: from
atob - traps: when
aandbare in different trees of a forest
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.path(3, 2) == [3, 1, 0, 2] and t.path(4, 4) == [4]
Rooted.diameter
fn diameter(self) -> (len: Int, u: V, v: V)A longest simple path in the tree holding t.root: (len, u, v) with
t.dist(u, v) == len, by two sweeps: u is farthest from the root, v farthest from u.
- cost: O(n)
- ties: in each sweep the farthest vertex first in
t.Preorder - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.diameter() == (len: 3, u: 3, v: 2)
Rooted.ancestor
fn ancestor(self, v: V, k: Int) -> ?VThe ancestor k edges above v (v itself for k == 0), or None if that is above the
root.
- cost: O(log n)
- traps: when
kis negative
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.ancestor(3, 2) == Some(0) and t.ancestor(3, 3) == None and t.ancestor(3, 0) == Some(3)
Rooted.jump
fn jump(self, a: V, b: V, k: Int) -> ?VThe vertex k edges from a on the path to b (a for k == 0), or None if the path
is shorter.
- cost: O(log n)
- traps: when
kis negative, oraandbare in different trees
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.jump(3, 2, 2) == Some(0) and t.jump(3, 2, 3) == Some(2) and t.jump(3, 2, 4) == None
Rooted.jump_while
fn jump_while(self, v: V, pred: V -> Bool) -> ?VThe highest ancestor u of v such that pred(u) holds, or None when pred(v) is false.
pred must be true and then false on the way up, and is checked only where the search
probes it.
- cost: O(log² n) calls of
pred - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.jump_while(3, v => v != 0) == Some(1) and t.jump_while(3, v => v == 0) == None
Rooted.chains
fn chains( self, a: V, b: V, edges: Bool = false, ) -> yields (range: Range<Pre>, rising: Bool)The path from a to b as O(log n) heavy-chain ranges of t.Pre, in path order. A
rising range is walked from its high end to its low end. With edges, the highest vertex
of the path is left out: for a value per edge, stored at the edge's lower end.
- cost: O(log n) ranges
- empty: with
edgesanda == b, nothing; otherwise never empty - order: from
atob - traps: when
aandbare in different trees of a forest
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.chains(3, 2).map(c => c.rising).collect() == [true, false] and t.chains(3, 2, edges: true).count() == 2
Rooted.fold_path
fn fold_path<S, T>(self, a: V, b: V, ds: S, edges: Bool = false) -> TThe fold of the values on the path from a to b, in that order, read from ds: any
structure over t.Pre with fold(range) and a monoid (SegTree).
A stretch of the path that climbs is folded top-down by ds and then turned round with
rev(): a value that is not its own reverse implements Reversible. With edges, the
value at the lowest common ancestor is left out.
- cost: O(log² n) with one structure
- empty: the identity for
a == bwithedges - traps: when
aandbare in different trees of a forest
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let seg = SegTree(+, t.reorder([1, 2, 4, 8, 16])); t.fold_path(3, 2, seg) == 15 and t.fold_path(3, 2, seg, edges: true) == 14
Rooted.apply_path
fn apply_path<S, F>(self, a: V, b: V, mut ds: S, tag: F, edges: Bool = false)Applies the update tag to every vertex on the path from a to b, through
ds.apply(range, tag) once per chain range. With edges, the lowest common ancestor is
left out.
- cost: O(log² n)
- empty: nothing changes for
a == bwithedges - traps: when
aandbare in different trees of a forest
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); var seg = SegTree(+, t.reorder([0, 0, 0, 0, 0]), act: add); t.apply_path(3, 2, seg, 5); t.fold_path(3, 2, seg) == 20 and seg.fold(t.sub(1)) == 10
Rooted.virtual
fn virtual(self, keys: List<V>) -> VirtualTree<V, _>The tree squeezed down to keys: the keys and the lowest common ancestor of every pair, in
a fresh domain vt.K in preorder, so for x in vt.K.rev visits children first.
vt.at[x] is the vertex, vt.parent[x] its nearest kept ancestor, vt.w[x] the
weighted distance to it (0 at the top) and vt.key[x] whether it is a key. Repeated keys
count once.
- cost: O(k log k + k log n) for k keys
- empty:
keysempty gives an emptyvt.K - order:
vt.Kint.Preorder - traps: when the keys are in different trees of a forest
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let vt = t.virtual([4, 3]); vt.at == [1, 3, 4] and vt.key == [false, true, true] and vt.w == [0, 1, 1]
Rooted.w
fn w(self, v: V) -> IntThe edge length from v up to its parent: 0 at a root, 1 unless the arcs are Weighted.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.w(3) == 1 and t.w(0) == 0
Rooted.ancestors
fn ancestors(self, v: V) -> yields Vv, its parent, and so on up to its root.
- cost: O(1) per vertex, O(depth(v)) in all
- empty: never empty; it starts with
v - order: from
vup - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.ancestors(3).collect() == [3, 1, 0]
Rooted.top
fn top(self, v: V) -> VThe top of the heavy chain through v: the highest vertex reached by heavy edges.
- cost: O(1)
- ties: None; the heavy children fix the chain
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.top(3) == 0 and t.top(4) == 4 and t.top(2) == 2
Rooted.chain
fn chain(self, v: V) -> Range<Pre>The heavy chain through v as one range of positions, its top first.
- cost: O(1)
- empty: never empty
- order: top first, down the chain
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.chain(3).map(p => t.at[p]).collect() == [0, 1, 3] and t.chain(2).count() == 1
Rooted.sub_at
fn sub_at(self, v: V, root: V) -> yields Range<Pre>The subtree of v were the tree rooted at root, as at most two ranges of positions:
sub(v) when root is outside it, all of t.Pre when v == root, and otherwise
everything except the subtree of the child of v toward root.
- cost: O(log n)
- empty: empty ranges are skipped, so one or two ranges come out
- order: increasing positions
- traps: when
vandrootare in different trees of a forest
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.sub_at(1, 3).flat_map(r => r.map(p => t.at[p])).collect() == [0, 1, 4, 2] and t.sub_at(1, 2).count() == 1
Rooted.on_path
fn on_path(self, c: V, a: V, b: V) -> BoolWhether c lies on the path from a to b, ends included.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.on_path(1, 3, 2) and t.on_path(3, 3, 2) and not t.on_path(4, 3, 2)
Rooted.meet
fn meet(self, a: V, b: V, c: V) -> VThe one vertex on all three paths between a, b and c: the deepest of their pairwise
lowest common ancestors.
- cost: O(log n)
- traps: when the three are not in one tree
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.meet(3, 4, 2) == 1 and t.meet(3, 2, 0) == 0
Rooted.above
fn above<T, U, M>( self, op: M, lift: (T, V, V) -> U = (x, c, p) => x, finish: (U, V) -> T, ) -> [V]?TThe other half of reroot: for v that is not a root, the DP of the tree without sub(v),
rooted at parent(v); None at a root. Takes the arguments of reroot, for answers that
are per edge rather than per vertex.
- cost: O(n) calls of
liftandfinish, O(n) calls ofop - empty: never empty
- order: keyed by
V - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.above(add, finish: (s, v) => s + 1) == [None, Some(2), Some(4), Some(4), Some(4)]
Rooted.farthest
fn farthest( self, x: ?(len: Int, u: V, v: V), y: ?(len: Int, u: V, v: V), ) -> ?(len: Int, u: V, v: V)The farthest pair among two vertex sets' farthest pairs, which is the farthest pair of
their union; None is the identity. As an operation value,
SegTree(op: (x, y) => t.farthest(x, y), id: None) keeps the diameter of any range of
vertices under changes.
- cost: O(log n): at most four
distcalls - ties: the first longest of
x,y,(x.u, y.u),(x.u, y.v),(x.v, y.u),(x.v, y.v) - traps: when the vertices are in different trees of a forest
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.farthest(Some((len: 0, u: 3, v: 3)), Some((len: 0, u: 2, v: 2))) == Some((len: 3, u: 3, v: 2)) and t.farthest(None, None) == None
Rooted.layers
fn layers(self) -> Layers<V, _>Every vertex ordered by depth, each depth in t.Pre order, over a fresh domain, so the
descendants of v at one depth are one range.
- cost: O(n)
- empty: never empty
- order: by depth, then
t.Pre - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let ly = t.layers(); ly.level(1).map(b => ly.at[b]).collect() == [1, 2]
Rooted.events
fn events(self) -> Events<V, _>The 2n enter and exit events of tour over a fresh domain, for Mo's algorithm on paths and
on subtrees.
- cost: O(n)
- empty: never empty
- order:
tourorder - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let ev = t.events(); ev.sub(1).count() == 6
Rooted.euler_tour
fn euler_tour<K: Ord>(self, by: V -> K = _ => ()) -> yields VThe closed Euler walk: 2n - 1 visits from the root back to it, each pair of neighbours
joined by a tree edge, children in t.Pre order. by: reorders each vertex's children
by a key, stably, so by: c => c in deep walks the children in deep last. A walk that
visits every vertex of a connected graph is Rooted(g, root: r).euler_tour(). A forest
walks only the first tree.
- cost: O(1) per item
- empty: never empty;
[r]for a single vertex - order: walk order from the root
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.euler_tour().collect() == [0, 1, 3, 1, 4, 1, 0, 2, 0]domain V = 0..3; let adj: [V]List<V> = [[1, 2], [0], [0]]; let t = Rooted(adj, root: 0); t.euler_tour(by: c => c == 1).collect() == [0, 2, 0, 1, 0]
Rooted.long_paths
fn long_paths(self) -> LongPaths<V, _>The long-path decomposition, for DP indexed by depth merged in O(n) in total. The tallest child is the first in child order on ties.
- cost: O(n)
- empty: never empty
- ties: the first tallest child in child order
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let lp = t.long_paths(); lp.height == [2, 1, 0, 0, 0] and lp.deep[1] == Some(3)
Rooted.preorder
fn preorder(self, v: V) -> yields Step<V>The subtree of v in t.Pre order as std.dp steps: step.state is the vertex,
step.depth its depth below v, and step.prune() skips the rest of its subtree
(decision 126).
- cost: O(size(v)), less when pruned
- empty: never empty; it starts with
v - order:
t.Preorder - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); t.preorder(1).map(s => (s.state, s.depth)).collect() == [(1, 0), (3, 1), (4, 1)]
VirtualTree
pub struct VirtualTree<V, K>A virtual tree from Rooted.virtual: a few vertices of a tree and their pairwise lowest
common ancestors, over its own domain K in preorder.
Centroids
pub struct Centroids<V>A centroid decomposition: the centroid of the tree, then recursively of each piece left when
it is removed. Every path passes through the centroid ancestor that first separates its
ends, and each vertex has at most log2 n + 1 centroid ancestors, so a question about all
paths through v is a loop over ancestors(v).
Built in O(n log n) time and memory without recursion.
Centroids.anc
anc: [V]List<(c: V, dist: Int, branch: V)>For each vertex, every centroid whose piece holds it, nearest first, with the distance and the neighbour of the centroid it hangs off.
Centroids.held
held: [V]List<V>For each centroid, the vertices of its piece in breadth-first order from it.
Centroids.new
fn new(next: Next<V>) -> Centroids<V>Decomposes the tree given by next (as for Rooted: a Graph, neighbour lists or a fn).
The first centroid is Rooted(next, root: V.first).centroid(). Each piece left by removing
a centroid c is rooted at its neighbour of c and gets the centroid nearer that root, the
pieces taken in the order next lists c's neighbours. Built without recursion.
- cost: O(n log n) time and memory
- ties: of two centroids in a piece, the one nearer the piece's root
- traps: when
nextis not a connected tree
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let cd = Centroids(adj); cd.root == 1 and cd.parent(2) == Some(0)
Centroids.parent
fn parent(self, c: V) -> ?VThe parent of centroid c in the centroid tree; None at cd.root.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let cd = Centroids(adj); cd.parent(0) == Some(1) and cd.parent(1) == None
Centroids.depth
fn depth(self, c: V) -> IntThe depth of c in the centroid tree, at most log2 n.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let cd = Centroids(adj); cd.depth(1) == 0 and cd.depth(3) == 1 and cd.depth(2) == 2
Centroids.ancestors
fn ancestors(self, v: V) -> yields (c: V, dist: Int)Every centroid whose piece holds v, with the tree distance from it: v itself at distance
0, then up the centroid tree. At most log2 n + 1 entries, no allocation.
- cost: O(1) per entry, O(log n) in all
- empty: never empty; it starts with
(c: v, dist: 0) - order: nearest centroid first, up to
cd.root - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let cd = Centroids(adj); cd.ancestors(2).collect() == [(c: 2, dist: 0), (c: 0, dist: 1), (c: 1, dist: 2)]
Centroids.piece
fn piece(self, c: V) -> yields (v: V, dist: Int, branch: V)The piece of centroid c: each vertex v, its distance from c, and branch, the
neighbour of c on the way to v (c itself for v == c). Pairs in different branches are
exactly the paths whose highest centroid is c.
- cost: O(size of the piece)
- empty: never empty; it starts with
(v: c, dist: 0, branch: c) - order: breadth-first from
c, neighbours in the ordernextlists them - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let cd = Centroids(adj); cd.piece(0).collect() == [(v: 0, dist: 0, branch: 0), (v: 2, dist: 1, branch: 2)] and cd.piece(1).count() == 5
Word
impl Reversible for WordWord.rev
fn rev(self) -> WordJumpTree
pub struct JumpTree<V>A rooted forest grown one leaf at a time, by skew-binary jump pointers: add is O(1),
queries are O(log n), and it keeps three arrays. Every vertex starts as its own root.
JumpTree.new
fn new() -> JumpTree<V>A forest of lone vertices, each its own root.
- cost: O(n)
- traps: never
Examples:
domain V = 0..4; let j = JumpTree<V>(); j.parent(2) == None and j.root_of(2) == 2
JumpTree.add
fn add(mut self, v: V, p: V)Hangs v, a lone vertex not yet in any tree, below p, setting its skew-binary jump
pointer from p's.
- cost: O(1)
- traps: when
valready has a parent, orv == p
Examples:
domain V = 0..4; var j = JumpTree<V>(); j.add(1, 0); j.add(2, 1); j.add(3, 1); j.parent(2) == Some(1) and j.depth(3) == 2
JumpTree.parent
fn parent(self, v: V) -> ?VThe parent of v, or None at a root.
- cost: O(1)
- traps: never
Examples:
domain V = 0..4; var j = JumpTree<V>(); j.add(1, 0); j.add(2, 1); j.add(3, 1); j.parent(1) == Some(0) and j.parent(0) == None
JumpTree.depth
fn depth(self, v: V) -> IntThe number of edges from v up to its root.
- cost: O(1)
- traps: never
Examples:
domain V = 0..4; var j = JumpTree<V>(); j.add(1, 0); j.add(2, 1); j.add(3, 1); j.depth(0) == 0 and j.depth(2) == 2
JumpTree.root_of
fn root_of(self, v: V) -> VThe root of v's tree.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..4; var j = JumpTree<V>(); j.add(1, 0); j.add(2, 1); j.add(3, 1); j.root_of(3) == 0
JumpTree.ancestor
fn ancestor(self, v: V, k: Int) -> ?VThe ancestor k edges above v (v for k == 0), or None if that is above the root.
- cost: O(log n)
- traps: when
kis negative
Examples:
domain V = 0..4; var j = JumpTree<V>(); j.add(1, 0); j.add(2, 1); j.add(3, 1); j.ancestor(2, 2) == Some(0) and j.ancestor(2, 3) == None
JumpTree.lca
fn lca(self, a: V, b: V) -> ?VThe lowest common ancestor of a and b, or None in different trees.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..4; var j = JumpTree<V>(); j.add(1, 0); j.add(2, 1); j.add(3, 1); j.lca(2, 3) == Some(1) and j.lca(2, 0) == Some(0)domain V = 0..3; var j = JumpTree<V>(); j.add(1, 0); j.lca(1, 2) == None
JumpTree.jump_while
fn jump_while(self, v: V, pred: V -> Bool) -> ?VThe highest ancestor u of v such that pred(u) holds, or None when pred(v) is false.
pred must be true and then false on the way up.
- cost: O(log n) calls of
pred - traps: never
Examples:
domain V = 0..4; var j = JumpTree<V>(); j.add(1, 0); j.add(2, 1); j.add(3, 1); j.jump_while(2, v => v != 0) == Some(1) and j.jump_while(2, v => v == 0) == None
JumpTree.dist
fn dist(self, a: V, b: V) -> ?IntThe number of edges between a and b; None across trees.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..4; var j = JumpTree<V>(); j.add(1, 0); j.add(2, 1); j.add(3, 1); j.dist(2, 3) == Some(2) and j.dist(0, 0) == Some(0)
JumpTree.jump
fn jump(self, a: V, b: V, k: Int) -> ?VThe k-th vertex on the path from a to b (a is the 0th); None past b or across
trees.
- cost: O(log n)
- traps: when
kis negative
Examples:
domain V = 0..4; var j = JumpTree<V>(); j.add(1, 0); j.add(2, 1); j.add(3, 1); j.jump(2, 3, 1) == Some(1) and j.jump(2, 3, 2) == Some(3) and j.jump(2, 3, 3) == None
Lift
pub struct Lift<V, T>(op: (T, T) -> T, identity: T)Binary lifting over a fixed forest given by parent links, each carrying a value on the edge
up: O(n log n) build and memory, O(log n) queries. A forest that grows leaf by leaf is a
JumpTree; one that changes is a LinkCut.
Lift.new
fn new(par: [V]?(V, T), op: (T, T) -> T, identity: T) -> Lift<V, T>Binary lifting over the forest par: par[v] is v's parent with the value on the edge
to it, None at a root. op must be associative with identity identity; it need not
commute, since folds run from the lower end up.
- cost: O(n log n) time and memory
- traps: when the parent links have a cycle
Examples:
domain V = 0..4; let par: [V]?(V, Int) = [None, Some((0, 5)), Some((1, 2)), Some((1, 7))]; let l = Lift(par, op: (x, y) => x + y, identity: 0); l.fold(2, up_to: 0) == 7 and l.depth(3) == 2
Lift.of
fn of(next: V -> ?V) -> Lift<V, ()>Lifting over any partial successor function, such as "the next interval a greedy picks":
Lift.of(i => first_from(iv[i].r)). None ends a chain; the links must form a forest.
Edge values are (), so climb and ancestor are what it is for.
- cost: O(n log n) time and memory, n calls of
next - traps: when the links have a cycle
Examples:
domain I = 0..4; let l = Lift<I, ()>.of(i => if i < 3: Some(I(i + 1)) else: None); l.ancestor(0, 3) == Some(3) and l.depth(0) == 3
Lift.climb
fn climb(self, v: V, ok: V -> Bool) -> (steps: Int, at: V)Climbs from v while the next vertex up satisfies ok, which must hold on a prefix of
every root path: how many edges were climbed and where it stopped. Greedy "jump while the
next one still fits" counts are Lift.of(next).climb(v, ok).steps.
- cost: O(log n) calls of
ok - traps: never
Examples:
domain V = 0..4; let par: [V]?(V, Int) = [None, Some((0, 5)), Some((1, 2)), Some((1, 7))]; let l = Lift(par, op: (x, y) => x + y, identity: 0); l.climb(2, u => u != 0) == (steps: 1, at: 1) and l.climb(2, u => false) == (steps: 0, at: 2)
Lift.parent
fn parent(self, v: V) -> ?VThe parent of v, or None at a root.
- cost: O(1)
- traps: never
Examples:
domain V = 0..4; let par: [V]?(V, Int) = [None, Some((0, 5)), Some((1, 2)), Some((1, 7))]; let l = Lift(par, op: (x, y) => x + y, identity: 0); l.parent(2) == Some(1) and l.parent(0) == None
Lift.depth
fn depth(self, v: V) -> IntThe number of edges from v up to its root.
- cost: O(1)
- traps: never
Examples:
domain V = 0..4; let par: [V]?(V, Int) = [None, Some((0, 5)), Some((1, 2)), Some((1, 7))]; let l = Lift(par, op: (x, y) => x + y, identity: 0); l.depth(0) == 0 and l.depth(3) == 2
Lift.ancestor
fn ancestor(self, v: V, k: Int) -> ?VThe ancestor k edges above v (v for k == 0), or None if that is above the root.
- cost: O(log n)
- traps: when
kis negative
Examples:
domain V = 0..4; let par: [V]?(V, Int) = [None, Some((0, 5)), Some((1, 2)), Some((1, 7))]; let l = Lift(par, op: (x, y) => x + y, identity: 0); l.ancestor(3, 2) == Some(0) and l.ancestor(3, 3) == None
Lift.lca
fn lca(self, a: V, b: V) -> ?VThe lowest common ancestor of a and b, or None in different trees.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..4; let par: [V]?(V, Int) = [None, Some((0, 5)), Some((1, 2)), Some((1, 7))]; let l = Lift(par, op: (x, y) => x + y, identity: 0); l.lca(2, 3) == Some(1)
Lift.fold
fn fold(self, v: V, up_to u: V) -> TThe fold with op of the edge values from v up to its ancestor u, lowest first;
identity when u == v.
- cost: O(log n) calls of
op - traps: when
uis not an ancestor ofv
Examples:
domain V = 0..4; let par: [V]?(V, Int) = [None, Some((0, 5)), Some((1, 2)), Some((1, 7))]; let l = Lift(par, op: (x, y) => x + y, identity: 0); l.fold(2, up_to: 1) == 2 and l.fold(2, up_to: 0) == 7 and l.fold(2, up_to: 2) == 0
Lift.climb_while
fn climb_while(self, v: V, ok: T -> Bool) -> VThe highest ancestor u of v with ok(self.fold(v, up_to: u)), or v itself; ok must
turn false at most once on the way up, and holds for identity.
- cost: O(log n) calls of
okandop - traps: never
Examples:
domain V = 0..4; let par: [V]?(V, Int) = [None, Some((0, 5)), Some((1, 2)), Some((1, 7))]; let l = Lift(par, op: (x, y) => x + y, identity: 0); l.climb_while(2, s => s <= 5) == 1 and l.climb_while(2, s => s <= 7) == 0
LinkCut
pub struct LinkCut<V, T>(m: Monoid<T>)A forest that changes: link and cut edges, re-root anywhere, and fold or set vertex
values along paths, by a link-cut tree (splay trees over preferred paths). Values fold
with op; a value that is not its own reverse implements Reversible, as for
Rooted.fold_path. Every operation is amortized O(log n).
LinkCut.new
fn new<M>(op: M, a: ?[V]T = None) -> LinkCut<V, T>V.count single-vertex trees holding a, or the identity of op everywhere when a is
absent.
- cost: O(n)
- empty:
a: Nonefills every vertex with the identity - traps: never
Examples:
domain V = 0..3; var lc = LinkCut<V, Int>(+); lc.get(2) == 0 and not lc.connected(0, 1)
LinkCut.top
fn top(self, x: V) -> BoolLinkCut.turn
fn turn(mut self, x: V)LinkCut.push
fn push(mut self, x: V)LinkCut.pull
fn pull(mut self, x: V)LinkCut.rotate
fn rotate(mut self, x: V)LinkCut.splay
fn splay(mut self, x: V)LinkCut.access
fn access(mut self, x: V) -> VLinkCut.make_root
fn make_root(mut self, v: V)Makes v the root of its tree.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var lc = LinkCut(+, a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.make_root(0); lc.root_of(2) == 0
LinkCut.root_of
fn root_of(mut self, v: V) -> VThe root of the tree holding v: the last vertex made root there, by make_root, link,
lca or fold_path.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var lc = LinkCut(+, a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.root_of(0) == 2 and lc.root_of(3) == 3
LinkCut.connected
fn connected(mut self, u: V, v: V) -> BoolWhether u and v are in the same tree.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var lc = LinkCut(+, a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.connected(0, 2) and not lc.connected(0, 3)
LinkCut.link
fn link(mut self, u: V, v: V)Adds the edge u-v: u becomes the root of its tree, which hangs below v, so the
joined tree keeps v's root.
- cost: amortized O(log n), with one
root_ofto check the trees differ - traps: when
uandvare already in one tree
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var lc = LinkCut(+, a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.link(3, 0); lc.connected(3, 2) and lc.root_of(3) == 2
LinkCut.cut
fn cut(mut self, u: V, v: V)Removes the edge u-v.
- cost: amortized O(log n)
- traps: when there is no edge
u-v
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var lc = LinkCut(+, a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.cut(1, 2); not lc.connected(0, 2) and lc.connected(0, 1)
LinkCut.lca
fn lca(mut self, u: V, v: V, root: V) -> ?VThe lowest common ancestor of u and v when their tree is rooted at root, which
becomes its root; None unless all three are connected.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var lc = LinkCut(+, a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.lca(0, 2, 1) == Some(1) and lc.root_of(0) == 1 and lc.lca(0, 3, 1) == None
LinkCut.get
fn get(self, v: V) -> TThe value at v.
- cost: O(1)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var lc = LinkCut(+, a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.get(2) == 3
LinkCut.set
fn set(mut self, v: V, x: T)Sets the value at v to x.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var lc = LinkCut(+, a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.set(2, 10); lc.get(2) == 10 and lc.fold_path(0, 2) == 13
LinkCut.fold_path
fn fold_path(mut self, u: V, v: V) -> TThe fold of the values on the path from u to v, in that order; u becomes the root.
- cost: amortized O(log n)
- traps: when
uandvare in different trees
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var lc = LinkCut(+, a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.fold_path(0, 2) == 6 and lc.root_of(2) == 0 and lc.fold_path(1, 1) == 2
LinkCut.dist
fn dist(mut self, a: V, b: V) -> ?IntThe number of edges between a and b; None across trees.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var lc = LinkCut(+, a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.dist(0, 2) == Some(2) and lc.dist(0, 3) == None
LinkCut.jump
fn jump(mut self, a: V, b: V, k: Int) -> ?VThe k-th vertex on the path from a to b (a is the 0th); None past b or across
trees.
- cost: amortized O(log n)
- traps: when
kis negative
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var lc = LinkCut(+, a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.jump(0, 2, 1) == Some(1) and lc.jump(0, 2, 0) == Some(0) and lc.jump(0, 2, 3) == None
PreferredPaths
pub struct PreferredPaths<V>LinkCut with updates along a path: LazyLinkCut(act, a) with an add Action adds to every value on
a path and folds paths, under the same Action as SegTree(op, a, act:). Reversing a path must not
change how a tag acts, apply(f, x.rev(), k) == apply(f, x, k).rev(), which holds for every
commutative over. Every operation is amortized O(log n). Memory is about twice LinkCut's.
The preferred-path half of a link-cut tree over a fixed rooted tree: every node starts as its
own path. Counting "how many paths lie between v and the root" (colours painted along root
paths, access counts) reads off the switches each access makes.
PreferredPaths.new
fn new<P>(t: Rooted<V, P>) -> PreferredPaths<V>The preferred paths of t with every vertex its own path.
- cost: O(n)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); var pp = PreferredPaths(t); pp.access(0).count() == 0
PreferredPaths.access
fn access(mut self, v: V) -> yields (lost: ?V, gained: V)Makes the path from the root to v one preferred path, yielding each switch bottom-up:
gained is the top vertex of the path just joined to its parent, lost the top vertex of
the path that parent stopped preferring, if any. Counting "how many paths lie between v
and the root" reads off the switches.
- cost: amortized O(log n) switches
- empty: nothing when
vis already on the root's preferred path - order: bottom-up
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); var pp = PreferredPaths(t); pp.access(3).collect() == [(lost: None, gained: 3), (lost: None, gained: 1)] and pp.access(4).collect() == [(lost: Some(3), gained: 4)]
LazyLinkCut
pub struct LazyLinkCut<V, T, F>(act: Action<T, F>)LazyLinkCut.cnt
cnt: [V]0..=V.countThe number of vertices in the splay subtree, the span that apply sees.
LazyLinkCut.new
fn new(act: Action<T, F>, a: ?[V]T = None) -> LazyLinkCut<V, T, F>V.count single-vertex trees holding a, or the identity of act.over everywhere when a
is absent.
- cost: O(n)
- empty:
a: Nonefills every vertex with the identity - traps: never
Examples:
domain V = 0..3; var lc = LazyLinkCut<V, Int, Int>(Action<Int, Int>(apply: (d, x, n) => x + d * n)); lc.get(1) == 0
LazyLinkCut.top
fn top(self, x: V) -> BoolLazyLinkCut.turn
fn turn(mut self, x: V)LazyLinkCut.put
fn put(mut self, x: V, f: F)LazyLinkCut.push
fn push(mut self, x: V)LazyLinkCut.pull
fn pull(mut self, x: V)LazyLinkCut.rotate
fn rotate(mut self, x: V)LazyLinkCut.splay
fn splay(mut self, x: V)LazyLinkCut.access
fn access(mut self, x: V) -> VLazyLinkCut.make_root
fn make_root(mut self, v: V)Makes v the root of its tree.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.make_root(0); lc.root_of(2) == 0
LazyLinkCut.root_of
fn root_of(mut self, v: V) -> VThe root of the tree holding v, as for LinkCut.root_of.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.root_of(0) == 2
LazyLinkCut.connected
fn connected(mut self, u: V, v: V) -> BoolWhether u and v are in the same tree.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.connected(0, 2)
LazyLinkCut.link
fn link(mut self, u: V, v: V)Adds the edge u-v as LinkCut.link does: u's tree hangs below v.
- cost: amortized O(log n), with one
root_ofto check the trees differ - traps: when
uandvare already in one tree
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.connected(0, 2) and lc.dist(0, 2) == Some(2)
LazyLinkCut.cut
fn cut(mut self, u: V, v: V)Removes the edge u-v.
- cost: amortized O(log n)
- traps: when there is no edge
u-v
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.cut(0, 1); not lc.connected(0, 2) and lc.connected(1, 2)
LazyLinkCut.lca
fn lca(mut self, u: V, v: V, root: V) -> ?VThe lowest common ancestor of u and v when their tree is rooted at root, which
becomes its root; None unless all three are connected.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.lca(0, 2, 1) == Some(1)
LazyLinkCut.get
fn get(mut self, v: V) -> TThe value at v, with every update along paths through it applied.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.apply_path(0, 1, 10); lc.get(1) == 12 and lc.get(2) == 3
LazyLinkCut.set
fn set(mut self, v: V, x: T)Sets the value at v to x, replacing every earlier update there.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.set(1, 7); lc.fold_path(0, 2) == 11
LazyLinkCut.fold_path
fn fold_path(mut self, u: V, v: V) -> TThe fold of the values on the path from u to v, in that order; u becomes the root.
- cost: amortized O(log n)
- traps: when
uandvare in different trees
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.fold_path(0, 2) == 6
LazyLinkCut.apply_path
fn apply_path(mut self, u: V, v: V, f: F)Applies f to every value on the path from u to v; u becomes the root.
- cost: amortized O(log n)
- traps: when
uandvare in different trees
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.apply_path(0, 1, 10); lc.fold_path(0, 2) == 26
LazyLinkCut.dist
fn dist(mut self, a: V, b: V) -> ?IntThe number of edges between a and b; None across trees.
- cost: amortized O(log n)
- traps: never
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.dist(0, 2) == Some(2) and lc.dist(1, 1) == Some(0)
LazyLinkCut.jump
fn jump(mut self, a: V, b: V, k: Int) -> ?VThe k-th vertex on the path from a to b (a is the 0th); None past b or across
trees.
- cost: amortized O(log n)
- traps: when
kis negative
Examples:
domain V = 0..3; let vals: [V]Int = [1, 2, 3]; var lc = LazyLinkCut(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); lc.link(0, 1); lc.link(1, 2); lc.jump(2, 0, 1) == Some(1) and lc.jump(2, 0, 3) == None
PermKind
pub enum PermKind = Leaf | Incr | Decr | Partial | FullHow a permutation-tree node joins its two children l (earlier positions) and r.
Incr: r's values sit just above l's; Decr: just below; Partial: the union is
not an interval on its own and only closes further up; Full: r fills the gaps of a
Partial l, closing an interval in neither order.
PermKind.Leaf
LeafPermKind.Incr
IncrPermKind.Decr
DecrPermKind.Partial
PartialPermKind.Full
FullPermNode
pub enum PermNode<I, N>: Leaf(i: I), Inner(l: N, r: N, kindA permutation-tree node as PermTree.node shows it: Leaf(i) for position i, or
Inner(l, r, kind) with its two children and how they join.
PermNode.Leaf
Leaf(i: I)PermNode.Inner
Inner(l: N, r: N, kind: PermKind)PermTree
pub struct PermTree<I, V, Node>The binary permutation (interval-decomposition) tree of a bijection p: [I]V: every node
covers a run of positions, leaves are single positions, a node's children split its run in
two, and the values of every node but a Partial one form an interval. Nodes have their own
domain t.Node of 2n - 1 members; kind, first, last, lo and hi are arrays over it.
Built in O(n) by one stack pass.
PermTree.new
fn new(p: [I]V) -> PermTree<I, V, _>The binary permutation tree of p, built by one stack pass from left to right: a run that
keeps extending in one direction builds left-deep, so [0, 1, 2] is ((0, 1), 2).
- cost: O(n)
- empty:
Imust be nonempty - traps: when
Iis empty,I.count != V.count, orpis not a bijection
Examples:
domain I = 0..3; let p: [I]I = [1, 0, 2]; let pt = PermTree(p); pt.kind[pt.root] == PermKind.Incr and pt.kind[pt.left(pt.root)] == PermKind.Decr
PermTree.node
fn node(self, v: Node) -> PermNode<I, Node>The view of v to match on (decision 132): Leaf(i) or Inner(l, r, kind).
- cost: O(1)
- traps: never
Examples:
domain I = 0..3; let p: [I]I = [1, 0, 2]; let pt = PermTree(p); pt.node(pt.leaf(1)) == PermNode.Leaf(1) and pt.node(pt.root) == PermNode.Inner(pt.left(pt.root), pt.leaf(2), PermKind.Incr)
PermTree.leaf
fn leaf(self, i: I) -> NodeThe leaf of position i.
- cost: O(1)
- traps: never
Examples:
domain I = 0..3; let p: [I]I = [1, 0, 2]; let pt = PermTree(p); pt.span(pt.leaf(2)) == 2..3 and pt.kind[pt.leaf(2)] == PermKind.Leaf
PermTree.left
fn left(self, v: Node) -> NodeThe earlier child of the inner node v.
- cost: O(1)
- traps: when
vis a leaf
Examples:
domain I = 0..3; let p: [I]I = [1, 0, 2]; let pt = PermTree(p); pt.span(pt.left(pt.root)) == 0..2
PermTree.right
fn right(self, v: Node) -> NodeThe later child of the inner node v.
- cost: O(1)
- traps: when
vis a leaf
Examples:
domain I = 0..3; let p: [I]I = [1, 0, 2]; let pt = PermTree(p); pt.right(pt.root) == pt.leaf(2)
PermTree.span
fn span(self, v: Node) -> Range<I>The positions v covers, a nonempty range of I.
- cost: O(1)
- empty: never empty
- order: increasing positions
- traps: never
Examples:
domain I = 0..3; let p: [I]I = [1, 0, 2]; let pt = PermTree(p); pt.span(pt.root) == 0..3
PermTree.vals
fn vals(self, v: Node) -> Range<V>From the least to the greatest value v covers: exactly its values unless v is Partial.
- cost: O(1)
- empty: never empty
- order: increasing values
- traps: never
Examples:
domain I = 0..3; let p: [I]I = [1, 0, 2]; let pt = PermTree(p); pt.vals(pt.left(pt.root)) == 0..2 and pt.vals(pt.leaf(0)) == 1..2
Layers
pub struct Layers<V, B>The vertices of a Rooted tree by depth, each depth in preorder, over their own domain
B: the descendants of a vertex at one depth are a contiguous range of B.
Layers.start
start: List<Int>The layer of depth d is start[d]..start[d + 1] as ordinals of B.
Layers.pos
fn pos(self, v: V) -> BThe position of v among the layers.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let ly = t.layers(); ly.at[ly.pos(2)] == 2
Layers.level
fn level(self, d: Int) -> Range<B>Every vertex at depth d, in t.Pre order; empty past the deepest or below 0.
- cost: O(1)
- empty: for
doutside0..=the greatest depth - order:
t.Preorder - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let ly = t.layers(); ly.level(2).map(b => ly.at[b]).collect() == [3, 4] and ly.level(3).count() == 0
Layers.below
fn below(self, v: V, d: Int) -> Range<B>The descendants of v at depth d, counted from the root as in level, by binary search
in level(d); v itself when d == depth(v).
- cost: O(log n)
- empty: when there are None, including
d < depth(v) - order:
t.Preorder - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let ly = t.layers(); ly.below(1, 2).map(b => ly.at[b]).collect() == [3, 4] and ly.below(2, 2).count() == 0
Events
pub struct Events<V, P>The enter and exit events of a Rooted tree's tour over their own domain P of 2n
members, for Mo's algorithm on trees.
Events.enter
fn enter(self, v: V) -> PThe event that enters v.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let ev = t.events(); ev.at[ev.enter(1)] == Enter(1, Some(0)) and ev.enter(1) < ev.enter(3)
Events.exit
fn exit(self, v: V) -> PThe event that leaves v.
- cost: O(1)
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let ev = t.events(); ev.at[ev.exit(3)] == Exit(3, Some(1)) and ev.exit(3) < ev.exit(1)
Events.sub
fn sub(self, v: V) -> Range<P>The events inside v's subtree, enter(v) through exit(v).
- cost: O(1)
- empty: never empty; 2 * size(v) events
- order:
tourorder - traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let ev = t.events(); ev.sub(1).map(p => ev.at[p]).collect() == [Enter(1, Some(0)), Enter(3, Some(1)), Exit(3, Some(1)), Enter(4, Some(1)), Exit(4, Some(1)), Exit(1, Some(0))]
Events.path
fn path(self, a: V, b: V) -> (range: Range<P>, extra: ?V)A range of events whose vertices met an odd number of times, plus extra when present, are
exactly the vertices of the path from a to b.
With a the end entered first: when a is an ancestor of b, the range is enter(a)
through enter(b) and extra is None; otherwise it is exit(a) through enter(b) and
extra is their lowest common ancestor.
- cost: O(log n)
- empty: never empty
- order:
tourorder - traps: when
aandbare in different trees
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let ev = t.events(); ev.path(3, 2).range.count() == 5 and ev.path(3, 2).extra == Some(0) and ev.path(1, 4).extra == None
LongPaths
pub struct LongPaths<V, L>The long-path decomposition of a Rooted tree: each vertex continues the path of its
tallest child, so a DP indexed by depth below v lives in one shared buffer over L,
inheriting deep[v]'s values is free, and merging the other children costs their heights.
LongPaths.deep
deep: [V]?VThe child with the tallest subtree; None at a leaf.
LongPaths.height
height: [V]IntThe number of edges on the longest path down from v.
LongPaths.slots
fn slots(self, v: V) -> Range<L>The slots of v, one per depth offset 0..=height[v], offset 0 first; slots(deep[v])
starts one later in the same buffer.
- cost: O(1)
- empty: never empty
- order: offset 0 first
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let lp = t.long_paths(); lp.slots(0).count() == 3 and lp.slots(2).count() == 1
LongPaths.slot
fn slot(self, v: V, d: Int) -> LThe slot of v at depth offset d.
- cost: O(1)
- traps: unless
0 <= d <= height[v]
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let lp = t.long_paths(); lp.slot(1, 1) == lp.slot(3, 0) and lp.slot(0, 1) == lp.slot(1, 0)
LcaTable
pub struct LcaTable<V>Lowest common ancestors in O(1) after O(n log n) preprocessing, by a sparse table over the
Euler tour: for many queries on a fixed tree when Rooted.lca is the bottleneck.
LcaTable.new
fn new<Pre>(t: Rooted<V, Pre>) -> LcaTable<V>A sparse table over the Euler walk of t, for O(1) lowest common ancestors on a fixed tree.
- cost: O(n log n) time and memory
- traps: never
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let lt = LcaTable(t); lt.lca(3, 4) == 1
LcaTable.lca
fn lca(self, a: V, b: V) -> VThe lowest common ancestor of a and b.
- cost: O(1)
- traps: when
aandbare in different trees
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let lt = LcaTable(t); lt.lca(3, 2) == 0 and lt.lca(4, 4) == 4
LcaTable.dist
fn dist(self, a: V, b: V) -> IntThe distance between a and b, weighted as the tree was built.
- cost: O(1)
- traps: when
aandbare in different trees
Examples:
domain V = 0..5; let adj: [V]List<V> = [[1, 2], [0, 3, 4], [0], [1], [1]]; let t = Rooted(adj, root: 0); let lt = LcaTable(t); lt.dist(3, 2) == 3
EulerTourTree
pub struct EulerTourTree<V, T>A forest that changes, with folds over whole trees and subtrees, by an Euler tour tree
(a balanced sequence of each tree's tour). Where LinkCut folds paths, this folds
components. Values fold with op, which must commute. Every operation is expected
O(log n).
EulerTourTree.new
fn new<M>(op: M, a: ?[V]T = None) -> EulerTourTree<V, T>Lone vertices with values a, or the identity of op everywhere when a is None.
- cost: O(n)
- empty:
a: Nonefills every vertex with the identity - traps: never
Examples:
domain V = 0..3; var et = EulerTourTree<V, Int>(+); et.get(1) == 0 and et.len(1) == 1
EulerTourTree.link
fn link(mut self, u: V, v: V)Joins the trees of u and v by the edge u-v.
- cost: expected O(log n)
- traps: when
uandvare already in one tree
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = EulerTourTree(+, a: Some(vals)); et.link(0, 1); et.link(1, 2); et.connected(0, 2) and et.len(2) == 3
EulerTourTree.cut
fn cut(mut self, u: V, v: V)Removes the edge u-v.
- cost: expected O(log n)
- traps: when there is no edge
u-v
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = EulerTourTree(+, a: Some(vals)); et.link(0, 1); et.link(1, 2); et.cut(1, 2); not et.connected(0, 2) and et.len(0) == 2
EulerTourTree.connected
fn connected(mut self, a: V, b: V) -> BoolWhether a and b are in one tree.
- cost: expected O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = EulerTourTree(+, a: Some(vals)); et.link(0, 1); et.link(1, 2); et.connected(0, 2) and not et.connected(0, 3)
EulerTourTree.len
fn len(mut self, v: V) -> IntThe number of vertices in v's tree.
- cost: expected O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = EulerTourTree(+, a: Some(vals)); et.link(0, 1); et.link(1, 2); et.len(0) == 3 and et.len(3) == 1
EulerTourTree.get
fn get(self, v: V) -> TThe value at v.
- cost: O(1)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = EulerTourTree(+, a: Some(vals)); et.link(0, 1); et.link(1, 2); et.get(3) == 4
EulerTourTree.set
fn set(mut self, v: V, x: T)Replaces the value at v.
- cost: expected O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = EulerTourTree(+, a: Some(vals)); et.link(0, 1); et.link(1, 2); et.set(0, 10); et.fold_tree(2) == 15
EulerTourTree.fold_tree
fn fold_tree(mut self, v: V) -> TThe fold of every value in v's tree.
- cost: expected O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = EulerTourTree(+, a: Some(vals)); et.link(0, 1); et.link(1, 2); et.fold_tree(0) == 6 and et.fold_tree(3) == 4
EulerTourTree.fold_sub
fn fold_sub(mut self, v: V, away: V) -> TThe fold over v's side of the edge v-away: what v's tree would hold were the edge
cut.
- cost: expected O(log n)
- traps: when there is no edge
v-away
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = EulerTourTree(+, a: Some(vals)); et.link(0, 1); et.link(1, 2); et.fold_sub(1, 2) == 3 and et.fold_sub(2, 1) == 3
LazyEulerTourTree
pub struct LazyEulerTourTree<V, T, F>EulerTourTree with updates to whole trees and subtrees under an action.
LazyEulerTourTree.new
fn new(act: Action<T, F>, a: ?[V]T = None) -> LazyEulerTourTree<V, T, F>Lone vertices with values a, or the identity of act.over everywhere when a is None.
- cost: O(n)
- empty:
a: Nonefills every vertex with the identity - traps: never
Examples:
domain V = 0..3; var et = LazyEulerTourTree<V, Int, Int>(Action<Int, Int>(apply: (d, x, n) => x + d * n)); et.get(1) == 0
LazyEulerTourTree.link
fn link(mut self, u: V, v: V)Joins the trees of u and v by the edge u-v.
- cost: expected O(log n)
- traps: when
uandvare already in one tree
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = LazyEulerTourTree(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); et.link(0, 1); et.link(1, 2); et.connected(0, 2) and et.len(2) == 3
LazyEulerTourTree.cut
fn cut(mut self, u: V, v: V)Removes the edge u-v.
- cost: expected O(log n)
- traps: when there is no edge
u-v
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = LazyEulerTourTree(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); et.link(0, 1); et.link(1, 2); et.cut(1, 2); not et.connected(0, 2)
LazyEulerTourTree.connected
fn connected(mut self, a: V, b: V) -> BoolWhether a and b are in one tree.
- cost: expected O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = LazyEulerTourTree(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); et.link(0, 1); et.link(1, 2); not et.connected(0, 3)
LazyEulerTourTree.len
fn len(mut self, v: V) -> IntThe number of vertices in v's tree.
- cost: expected O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = LazyEulerTourTree(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); et.link(0, 1); et.link(1, 2); et.len(1) == 3
LazyEulerTourTree.get
fn get(mut self, v: V) -> TThe value at v, with every update to a tree or side holding it applied.
- cost: expected O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = LazyEulerTourTree(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); et.link(0, 1); et.link(1, 2); et.apply_tree(0, 10); et.get(2) == 13 and et.get(3) == 4
LazyEulerTourTree.set
fn set(mut self, v: V, x: T)Replaces the value at v, discarding earlier updates there.
- cost: expected O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = LazyEulerTourTree(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); et.link(0, 1); et.link(1, 2); et.set(0, 10); et.fold_tree(2) == 15
LazyEulerTourTree.fold_tree
fn fold_tree(mut self, v: V) -> TThe fold of every value in v's tree.
- cost: expected O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = LazyEulerTourTree(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); et.link(0, 1); et.link(1, 2); et.fold_tree(0) == 6
LazyEulerTourTree.fold_sub
fn fold_sub(mut self, v: V, away: V) -> TThe fold over v's side of the edge v-away.
- cost: expected O(log n)
- traps: when there is no edge
v-away
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = LazyEulerTourTree(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); et.link(0, 1); et.link(1, 2); et.fold_sub(1, 2) == 3
LazyEulerTourTree.apply_tree
fn apply_tree(mut self, v: V, f: F)Applies f to every value in v's tree.
- cost: expected O(log n)
- traps: never
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = LazyEulerTourTree(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); et.link(0, 1); et.link(1, 2); et.apply_tree(0, 10); et.fold_tree(2) == 36 and et.get(3) == 4
LazyEulerTourTree.apply_sub
fn apply_sub(mut self, v: V, away: V, f: F)Applies f to every value on v's side of the edge v-away.
- cost: expected O(log n)
- traps: when there is no edge
v-away
Examples:
domain V = 0..4; let vals: [V]Int = [1, 2, 3, 4]; var et = LazyEulerTourTree(Action<Int, Int>(apply: (d, x, n) => x + d * n), a: Some(vals)); et.link(0, 1); et.link(1, 2); et.apply_sub(1, 2, 10); et.get(0) == 11 and et.get(2) == 3 and et.fold_tree(0) == 26
KruskalTree
pub struct KruskalTree<V, N, W>The Kruskal reconstruction tree: each edge that merges two components, in increasing
weight, becomes a node above them. The leaves under a node are the vertices connected by
edges of weight at most its own, so "what v reaches under a limit" is one subtree.
KruskalTree.leaf
leaf: [V]NThe leaf node of each vertex.
KruskalTree.w
w: [N]?WThe merging weight of each node; None at a leaf.
KruskalTree.tree
fn tree(self) -> Rooted<N, _>The nodes as a Rooted forest over N: subtree ranges, LCA and folds. The roots, one per
component, are in increasing node order.
- cost: O(1); built with the tree
- traps: never
Examples:
domain V = 0..3; let es: [0..2](u: V, v: V, w: Int) = [(u: 0, v: 1, w: 5), (u: 1, v: 2, w: 3)]; let (domain N, kt) = kruskal_tree(es, w: e => es[e].w); kt.tree.parent(kt.leaf[1]) == kt.tree.parent(kt.leaf[2]) and kt.tree.size(kt.leaf[0]) == 1
KruskalTree.reach
fn reach(self, v: V, limit: W) -> NThe highest node above leaf[v] whose weight is at most limit (leaf[v] itself when
None is); its leaves are what v reaches by edges of weight at most limit.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..3; let es: [0..2](u: V, v: V, w: Int) = [(u: 0, v: 1, w: 5), (u: 1, v: 2, w: 3)]; let (domain N, kt) = kruskal_tree(es, w: e => es[e].w); kt.reach(0, 4) == kt.leaf[0] and kt.w[kt.reach(1, 4)] == Some(3) and kt.w[kt.reach(1, 5)] == Some(5)
KruskalTree.top
fn top<E>(self, v: V, ok: E -> Bool) -> NThe highest node above leaf[v] whose merging edge, and every one below it, satisfies ok,
which gets the edge's key in the list given to kruskal_tree
(kt.top(v, ok: e => roads[e].alt > p)). ok must hold on a prefix of the merge order.
- cost: O(log n) calls of
ok - ties: None; the highest such node is unique
- traps: never
Examples:
domain V = 0..3; let es: [0..2](u: V, v: V, w: Int) = [(u: 0, v: 1, w: 5), (u: 1, v: 2, w: 3)]; let (domain N, kt) = kruskal_tree(es, w: e => es[e].w); kt.w[kt.top(1, e => es[e].w < 5)] == Some(3) and kt.top(0, e => false) == kt.leaf[0]
KruskalTree.up
fn up<T, M>(self, op: M, leaf: V -> T) -> [N]TFor every node, op folded over the leaf values of the leaves under it, in vertex order:
the least walk home from any vertex a subtree reaches is kt.up(min, leaf: v => home[v]!).
- cost: O(n) calls of
opandleaf - empty: never empty; every leaf has a value
- order: keyed by
N - traps: never
Examples:
domain V = 0..3; let es: [0..2](u: V, v: V, w: Int) = [(u: 0, v: 1, w: 5), (u: 1, v: 2, w: 3)]; let (domain N, kt) = kruskal_tree(es, w: e => es[e].w); let c = kt.up(add, leaf: v => 1); c[kt.reach(2, 3)] == 2 and c[kt.leaf[0]] == 1
KruskalTree.bottleneck
fn bottleneck(self, a: V, b: V) -> ?WThe least possible largest edge weight on a path from a to b: the weight of their
lowest common ancestor. None when they are not connected, and at a == b.
- cost: O(log n)
- traps: never
Examples:
domain V = 0..3; let es: [0..2](u: V, v: V, w: Int) = [(u: 0, v: 1, w: 5), (u: 1, v: 2, w: 3)]; let (domain N, kt) = kruskal_tree(es, w: e => es[e].w); kt.bottleneck(0, 2) == Some(5) and kt.bottleneck(1, 2) == Some(3) and kt.bottleneck(0, 0) == None