Heavy-Light Decomposition
In competitive programming, Heavy-Light Decomposition is a strategic approach for navigating and querying in trees. Heavy Light decomposition (HLD) is one of the most used techniques in competitive programming. HLD of a rooted tree is a method of decomposing the vertices of the tree into disjoint chains (no two chains share a node), to achieve important asymptotic time bounds for certain problems involving trees. HLD can also be seen as ‘coloring’ of the tree’s edges. The ‘Heavy-Light’ comes from the way we segregate edges. We use size of the subtrees rooted at the nodes as our criteria.
An edge is heavy if size(v) > size(u) where u is any sibling of v. If they come out to be equal, we pick any one such v as special. HLD constructs the tree into a set of chains or paths, where each chain is comprised of a heavy child and its light children. The heavy child refers to the child with the most descendants, while the light children refer to the remaining children. This decomposition strategically merges nodes into chains, prioritizing those with larger subtrees, thereby reducing the overall number of nodes to be traversed.
25 Essential Concepts for Competitive Programming
Competitive Programming is a mental sport which enables you to code a given problem under provided constraints. The purpose of this article is to provide an overview of the most frequent tricks used in Competitive Programming.
These 25 tricks will help you master competitive programming and solve the problems efficiently: