Module linkcut 

Link-Cut Trees for dynamic tree operations

Provides O(log n) amortized operations for:

• Link: Connect two trees
• Cut: Disconnect a subtree
• Path queries: Aggregate values on root-to-node paths
• Connectivity: Check if two nodes are in same tree

Based on Sleator-Tarjan’s Link-Cut Trees using splay trees.

Performance Optimizations

This implementation includes several optimizations:

• Path compression in find_root for O(log n) amortized complexity
• Optimized zig-zig and zig-zag splay patterns for better cache locality
• Lazy aggregation for efficient path queries
• Inline hints for hot path functions
• Cold hints for error paths
• Pre-allocation with capacity hints
• Node caching for frequently accessed roots

Structs

LinkCutTree

Link-Cut Tree supporting dynamic tree operations

Type Aliases

NodeId

Node identifier