Heavy-Light Decomposition
Author: Benjamin Qi
Path and subtree updates and queries.
Focus Problem – read through this problem before continuing!
Focus Problem – read through this problem before continuing!
Tutorial
| Resources | |||
|---|---|---|---|
| cp-algo | For an alternate implementation, see below | ||
| CF | blog + video for USACO Cowland. Binary jumping isn't necessary though. | ||
| anudeep2011 | explains what HLD is (but incomplete & overly complicated code) | ||
Optional: Tree Queries in O(NQ)
This is why you don't set problems where is intended ...
Implementations
| Resources | |||
|---|---|---|---|
| CF | |||
| CF | not complete | ||
| Benq | complete implementation following the above two articles with minor modifications | ||
This section is not complete.
Problems
A
There are better solutions than HLD (but it works)!
| Status | Source | Problem Name | Difficulty | Tags | |||||
|---|---|---|---|---|---|---|---|---|---|
| Gold | Easy | Show TagsHLD | |||||||
| Gold | Easy | Show TagsHLD, PURS | |||||||
| Plat | Normal | Show TagsHLD | |||||||
B
HLD is intended.
| Status | Source | Problem Name | Difficulty | Tags | |||||
|---|---|---|---|---|---|---|---|---|---|
| CSES | Easy | ||||||||
| Old Gold | Normal | Show TagsHLD, PURS | |||||||
| YS | Normal | Show TagsHLD, SegTree | |||||||
| CF | Hard | Show TagsHLD | |||||||
| TLX | Hard | ||||||||
| JOI | Hard | Show TagsHLD | |||||||
| JOI | Very Hard | Show TagsHLD | |||||||
Warning!
"Grass Planting" isn't submittable on the USACO website. Use this link to submit.
Module Progress:
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!