Concepts6
Problem Classification Patterns
Many competitive programming problems map to a small set of classic patterns; recognizing keywords and constraints lets you pick the right tool fast.
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.
LCA - Binary Lifting
Binary lifting precomputes 2^k ancestors for every node so we can jump upward in powers of two.
Bridge Tree
A bridge tree is built by contracting every 2-edge-connected component of an undirected graph into a single node, leaving only bridges as edges between nodes.
Tree Distances and Diameter
Tree diameter is the longest simple path in a tree and can be found with two BFS/DFS runs.