Rare
0/11
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.
Any help would be appreciated! Just submit a Pull Request on Github.
Problems
A
There are better solutions than HLD (but it works)!
| Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
|---|---|---|---|---|---|---|
| Gold | Easy | Show TagsHLD | External Sol | |||
| Gold | Easy | Show TagsPURS, HLD | External Sol | |||
| Plat | Normal | Show TagsHLD | External Sol |
B
HLD is intended.
| Status | Source | Problem Name | Difficulty | Tags | Solution | URL |
|---|---|---|---|---|---|---|
| Old Gold | Normal | Show TagsHLD, PURS | External Sol | |||
| YS | Normal | Show TagsHLD, SegTree | Show Sketch | |||
| CF | Hard | Show TagsHLD | Check CF | |||
| TLX | Hard | View Solution | ||||
| JOI | Hard | Show TagsHLD | Show Sketch | |||
| JOI | Very Hard | Show TagsHLD | External Sol |
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!
Give Us Feedback on Heavy-Light Decomposition!
Leave suggestions for us by making a post on the USACO Forum! Ex: Unclear sections, mislabeled problems, etc.