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!