Struct Tree 

pub struct Tree { /* private fields */ }

A rooted tree built over a Graph, with the LCA / subtree query structures precomputed.

Construct with Tree::new / [tree_from_edges]; both validate the acyclic + connected invariant and root the tree (default root 0).

Stored structure

All arrays are indexed by vertex id and length n:

• parent[v] — v’s parent, or v itself for the root (a self-parent sentinel — cheap and unambiguous since the root is the only self-parent).
• depth[v] — edges from the root to v (root has depth 0).
• tin[v] / tout[v] — the half-open preorder interval [tin, tout) of v’s subtree. u is an ancestor of v iff tin[u] <= tin[v] < tout[u]; subtree_size(v) == tout[v] - tin[v].
• preorder — the preorder sequence (length n); preorder[tin[v]] == v.
• the Euler tour euler (length 2n - 1) of vertices in the order first-and-on-each-return visited, first[v] its first occurrence, and a sparse table over the tour’s depths for O(1) RMQ (the LCA).
• up — the binary-lifting ancestor table (up[k][v] is v’s 2^k-th ancestor), backing kth_ancestor.

Implementations

impl Tree

pub fn new( n: usize, edges: &[(u32, u32)], root: Option<u32>, ) -> Result<Tree, TreeError>

Build a rooted tree from n vertices and an edge list, validating the acyclic + connected invariant.

edges is (u, v) unordered pairs (the tree is undirected). root selects the root; None defaults to vertex 0.

Errors

• TreeError::EmptyTree if n == 0.
• TreeError::RootOutOfRange if root >= n.
• TreeError::WrongEdgeCount if the edge count is not n - 1.
• TreeError::NotConnected if the graph is not connected. (Connected + n - 1 edges ⟺ a tree, so these two checks suffice; a > n - 1 edge count surfaces as WrongEdgeCount.)

pub fn from_graph(graph: Graph, root: Option<u32>) -> Result<Tree, TreeError>

Validate an existing graph as an unweighted, undirected tree and root it.

The graph value is consumed, but the tree stores a canonical edge order so construction order and endpoint orientation are not tree identity.

pub fn order(&self) -> usize

The number of vertices.

pub fn root(&self) -> u32

The root vertex.

pub fn graph(&self) -> &Graph

The underlying undirected Graph.

pub fn parent(&self, v: u32) -> Option<u32>

v’s parent, or None if v is the root.

pub fn children(&self, v: u32) -> &[u32]

v’s children, in ascending id order.

pub fn depth(&self, v: u32) -> usize

v’s depth — edges from the root to v (the root has depth 0).

pub fn kth_ancestor(&self, v: u32, k: usize) -> Option<u32>

v’s k-th ancestor (parent for k == 1), or None if k exceeds v’s depth. kth_ancestor(v, 0) == Some(v).

O(log n) via the binary-lifting table.

pub fn is_ancestor(&self, a: u32, d: u32) -> bool

true if a is an ancestor of d (a vertex is its own ancestor).

O(1) via the preorder interval: a is an ancestor of d iff d lies in a’s subtree interval [tin[a], tout[a]).

pub fn subtree_size(&self, v: u32) -> usize

The number of vertices in v’s subtree (including v). O(1).

pub fn subtree(&self, v: u32) -> &[u32]

v’s subtree as a preorder slice (it begins with v). O(1) to obtain; length subtree_size(v).

pub fn preorder(&self) -> &[u32]

The whole preorder sequence (length n), beginning with the root.

pub fn lca(&self, u: u32, v: u32) -> u32

The lowest common ancestor of u and v. O(1) after the O(n log n) Euler-tour sparse-table prep done at construction.

The LCA is the vertex of minimum depth on the Euler-tour segment between u’s and v’s first occurrences.

pub fn distance(&self, u: u32, v: u32) -> usize

The tree distance between u and v — depth(u) + depth(v) − 2·depth(lca).

pub fn fold<S>( &self, leaf: impl Fn(u32) -> S, merge: impl Fn(&S, u32, &S) -> S, ) -> Vec<S>

where S: Clone,

A generic deep-safe post-order subtree fold.

For each vertex, in post-order (children before parent), merge(child_state, child_id, partial) accumulates the children’s states into a parent value seeded by leaf(v). Returns the per-vertex result vector (indexed by vertex id).

The iteration is the reverse preorder — a child always precedes its parent there, so a single linear pass suffices and there is no recursion (deep-safe on P_n at n = 1_000_000).

leaf(v) produces the base state for v (before folding its children); merge(&acc, child, &child_state) folds one child’s finished state into the running accumulator.

pub fn diameter(&self) -> (usize, Vec<u32>)

The tree’s diameter: the number of edges on a longest path, with a realizing path (a sequence of vertices). Works on the unrooted tree.

Double-BFS: the farthest vertex a from any start, then the farthest b from a; a‥b is a diameter. Returns (length, path) with the path running a → … → b.

pub fn center(&self) -> SmallVec2

The one or two vertices minimizing maximum distance to all vertices.

These are the middle vertices of any diameter path. This is the graph theoretic center, not the size-balanced centroid.

pub fn centroid(&self) -> SmallVec2

The tree’s centroid(s) — the size-balance definition: a vertex whose removal leaves no component with more than ⌊n/2⌋ vertices. A tree has one or two centroids (two iff n is even and they are adjacent).

Not Sage’s center (the eccentricity-minimising centre) — a distinct notion; the parity harness pins the size-balance definition.

pub fn centroid_decomposition(&self) -> CentroidTree

The recursive centroid decomposition as a [CentroidTree]: the centroid-decomposition parent of every vertex (the root has no parent). Each level halves the component size, so the decomposition has depth O(log n).

Deep-safe: the recursion over components uses an explicit work stack.

pub fn heavy_light_decomposition(&self) -> HeavyLightDecomposition

The heavy-light decomposition structure: per-vertex chain head, position within the linearised HLD order, and the heavy child.

This returns the HLD structure rather than a value-aggregation query engine. It is enough to decompose any u‥v tree path into O(log n) contiguous [lo, hi] position intervals via [HeavyLightDecomposition::path_intervals].

Trait Implementations

impl Clone for Tree

fn clone(&self) -> Tree

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for Tree

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for Tree

fn deserialize<D>( deserializer: D, ) -> Result<Tree, <D as Deserializer<'de>>::Error>

where D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Display for Tree

fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error>

Formats the value using the given formatter.

impl PartialEq for Tree

fn eq(&self, other: &Tree) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl SemanticType for Tree

const TYPE_ID: &'static str = "noether/combin/Tree@1"

Versioned, language-neutral semantic identity.

fn canonical_bytes(&self) -> Result<Vec<u8>, NoetherError>

Serialize without backend- or language-specific identity.

fn describe() -> &'static TypeDescription

Return static discovery metadata for the type.

impl Serialize for Tree

fn serialize<S>( &self, serializer: S, ) -> Result<<S as Serializer>::Ok, <S as Serializer>::Error>

where S: Serializer,

Serialize this value into the given Serde serializer.

impl Eq for Tree