HLD-SegmentTree

USACO 2019 February Contest, Gold

Heavy-Light Decomposition (HLD) allows tree paths from the child to the parent to be expressed as a contiguous subarray. We can then use a segment tree to update and get values in O(log n).

Problem:

• Problem link: http://www.usaco.org/index.php?page=viewproblem2&cpid=921
• Problem solution: http://www.usaco.org/current/data/sol_cowland_gold_feb19.html

Online material that I used:

• LCA: https://activities.tjhsst.edu/sct/lectures/1718/2017-12-01_Lowest_Common_Ancestor.pdf
• HLD: https://www.geeksforgeeks.org/heavy-light-decomposition-set-1-introduction/
• Segment tree: https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/