Struct LinkCutTree 

pub struct LinkCutTree { /* private fields */ }

Link-Cut Tree supporting dynamic tree operations

Implementations

impl LinkCutTree

pub fn new() -> Self

Create a new empty Link-Cut Tree

pub fn with_capacity(n: usize) -> Self

Create with capacity hint

Performance

Pre-allocates memory to avoid reallocation during tree construction

pub fn make_tree(&mut self, id: NodeId, value: f64) -> usize

Add a new node to the forest

pub fn link(&mut self, u: NodeId, v: NodeId) -> Result<()>

Link node v as child of node u Returns error if v is not a root or u and v are in same tree After this operation, v will be the parent of u in the represented tree

pub fn cut(&mut self, v: NodeId) -> Result<()>

Cut the edge from node v to its parent Returns error if v is already a root

pub fn find_root(&mut self, v: NodeId) -> Result<NodeId>

Find the root of the tree containing node v

Performance Optimizations

• Uses path compression: splays intermediate nodes to reduce future queries
• Caches root for O(1) lookups on subsequent queries
• Inline hint for hot path

pub fn connected(&mut self, u: NodeId, v: NodeId) -> bool

Check if two nodes are in the same tree

pub fn path_aggregate(&mut self, v: NodeId) -> Result<f64>

Get the path aggregate (e.g., minimum) from root to v

Performance

Uses lazy aggregation - aggregates are maintained incrementally

pub fn update_value(&mut self, v: NodeId, value: f64) -> Result<()>

Update the value at node v

pub fn lca(&mut self, u: NodeId, v: NodeId) -> Result<NodeId>

Get the Lowest Common Ancestor of u and v

pub fn len(&self) -> usize

Get the number of nodes

pub fn is_empty(&self) -> bool

Check if empty

pub fn bulk_link(&mut self, edges: &[(NodeId, NodeId)]) -> Result<()>

Bulk link operation for linking multiple nodes at once

Performance

More efficient than individual links due to batched cache invalidation

pub fn bulk_update(&mut self, updates: &[(NodeId, f64)]) -> Result<()>

Bulk update values for better cache performance

Performance

Batches updates to reduce overhead

Trait Implementations

impl Default for LinkCutTree

fn default() -> Self

Returns the “default value” for a type.