tpl_link_cut_tree_with_edges.H File Reference

Edge-weighted Link-Cut Tree using edge-as-node representation. More...

#include <functional>
#include <tpl_dynSetHash.H>
#include <tpl_link_cut_tree.H>

Include dependency graph for tpl_link_cut_tree_with_edges.H:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
class	Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >
	Link-Cut Tree with edge weights and path aggregations. More...
struct	Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::EdgeKey
struct	Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::EdgeKeyHash
struct	Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::EdgeKeyEq
struct	Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::NodePtrEq
struct	Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::EdgeRec
struct	Aleph::Gen_Link_Cut_Tree_WithEdges< VT, ET, EdgeMonoid, LazyTag >::ExportData
	Data stored in each exported Tree_Node. More...

Namespaces
namespace	Aleph
	Main namespace for Aleph-w library functions.

Typedefs
template<typename EdgeT = int, class Monoid = DefaultMonoid<EdgeT>>
using	Aleph::Link_Cut_Tree_WithEdges = Gen_Link_Cut_Tree_WithEdges< int, EdgeT, Monoid >
	Convenience alias for edge-weighted Link-Cut Tree.

Detailed Description

Edge-weighted Link-Cut Tree using edge-as-node representation.

Extends the Link-Cut Tree to support edge values (weights). Each edge is internally represented as a hidden node in the underlying splay forest, placed between its two endpoint vertices. Vertex nodes carry the monoid identity so that path aggregations reflect edge values only.

Architecture

This class composes with Gen_Link_Cut_Tree<ET, EdgeMonoid, LazyTag>, delegating all splay/access/link/cut mechanics to the proven vertex-only implementation. An edge (u, v) with weight w becomes three internal nodes linked as u — edge_node(w) — v, where vertex nodes hold EdgeMonoid::identity() (transparent to aggregation).

Typical Use Cases

• Dynamic MST: query the max-weight edge on a cycle to decide which edge to swap (MaxMonoid).
• Bottleneck Paths: find the minimum-capacity edge on a path (MinMonoid).

Template Parameters

VT	Vertex payload type (not aggregated).
ET	Edge value type (aggregated via EdgeMonoid).
EdgeMonoid	Associative combiner for edge aggregation.
LazyTag	Lazy-tag policy for deferred edge updates.

Author

Leandro Rabindranath León

Definition in file tpl_link_cut_tree_with_edges.H.