Heavy-light Decompositions

Heavy-light decomposition of a tree is a powerful tool that often helps in the most difficult tree data structure problems. Heavy-light decomposition is to be built on a rooted tree. In this problem, the node with the number 1 should be considered the root of a tree. Heavy light decomposition is a colouring of edges of the tree. Each edge is either heavy or light. For each non leaf node (node ha