Concepts6
Dominator Tree
A dominator tree summarizes “must-pass” relationships in a directed graph from a chosen root r: u dominates v if every path from r to v goes through u.
Block-Cut Tree
A Block-Cut Tree decomposes an undirected graph into biconnected components (blocks) and articulation points, forming a bipartite tree.
Virtual Tree (Auxiliary Tree)
A Virtual Tree (Auxiliary Tree) compresses a large tree into a much smaller tree that contains only the k important nodes and the LCAs needed to keep them connected.
Link-Cut Tree
A Link-Cut Tree (LCT) maintains a dynamic forest and supports link, cut, and path queries in O(log n) amortized time.
Centroid Decomposition
Centroid decomposition splits a tree around a special node (centroid) so that every remaining component has at most half the nodes.
HLD - Path Queries and Updates
Heavy-Light Decomposition (HLD) breaks a tree into a small number of vertical chains so any path (u,v) becomes O(log n) contiguous segments in an array.