PrevNext
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-algoFor an alternate implementation, see below
CFblog + video for USACO Cowland. Binary jumping isn't necessary though.
anudeep2011explains 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
CFnot complete
Benqcomplete 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)!

StatusSourceProblem NameDifficultyTagsSolutionURL
GoldEasy
Show Tags

HLD

External Sol
GoldEasy
Show Tags

PURS, HLD

External Sol
PlatNormal
Show Tags

HLD

External Sol

B

HLD is intended.

StatusSourceProblem NameDifficultyTagsSolutionURL
Old GoldNormal
Show Tags

HLD, PURS

External Sol
YSNormal
Show Tags

HLD, SegTree

Show Sketch
CFHard
Show Tags

HLD

Check CF
TLXHardView Solution
JOIHard
Show Tags

HLD

Show Sketch
JOIVery Hard
Show Tags

HLD

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.

PrevNext