Graphs -> Centroid Decomposition¶

Balanced recursive tree splitting, centroid-tree ancestors, and path-through-centroid divide and conquer on static trees.

Microtopics¶

Source	Type
USACO Guide Centroid Decomposition	`Reference`
OI Wiki tree centroid	`Reference`
OI Wiki tree divide	`Reference`

Material	Type
Centroid hot sheet	`quick reference`
Centroid starter route	`starter route`
Ciel the Commander note	`anchor note`
Trees tutorial	`adjacent tutorial`
Heavy-Light Decomposition tutorial	`compare point`

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Finding a Centroid	`CSES`	`Medium`	Trees	Subtree Sizes; Balance Check; Candidate Descent	DFS; Subtree Sizes; Rooted Tree	Subtree Sizes; Balance Check	The cleanest warm-up for the centroid existence proof and the heavy-child walk used before full decomposition.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Ciel the Commander	`Codeforces`	`Hard`	Construction	Centroid Decomposition; Recursive Labeling; Tree Partition	Centroid Basics; Static Trees; Subtree Sizes	Centroid Tree; Recursive Labeling; Balanced Split	The strongest first full decomposition problem because the answer is literally the centroid-tree depth labeling.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Xenia and Tree	`Codeforces`	`Hard`	Queries	Centroid Ancestors; Distance Aggregation; Online Queries	Centroid Decomposition; Tree Distances; O(log N) Ancestor Walk	Nearest Marked Node; Centroid Ancestors; Distance Aggregation	The canonical update/query problem where each operation becomes a walk over one logarithmic centroid-ancestor chain.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Fixed-Length Paths I	`CSES`	`Hard`	Path Counting	Path Counting; Depth Collection; Frequency Merge	Centroid Decomposition; DFS Depth Collection; Frequency Counting	Exact Length; Depth Histogram; Through-Centroid Counting	The cleanest path-counting benchmark once you trust that every path is handled at the first centroid where its endpoints split.

Problem	Source	Difficulty	Context	Style	Prerequisites	Tags	Why it fits
Fixed-Length Paths II	`CSES`	`Hard`	Path Counting	Path Counting; Range Counting; Prefix Merge	Centroid Decomposition; Fixed-Length Paths I; Prefix Sums	Length Range; Depth Prefix Counts; Through-Centroid Counting	A natural next step after exact-length counting, where the merge logic becomes the real difficulty rather than the decomposition itself.

Code	Title	Fit	Difficulty	Pattern	Note	Solution
`CIELTHECOMMANDER`	Ciel the Commander	`primary`	`hard`	centroid decomposition; centroid tree labeling; balanced recursive split	Note	Code

python3 scripts/generate_problem_catalog.py