Skip to content

Centroid Decomposition Hot Sheet

Use this page when the tree is static and the clean split is “paths or updates through one balanced pivot” rather than one rooted subtree or one segment-tree-on-path reduction.

Do Not Use When

  • you only need one centroid node, not the full centroid tree
  • queries are subtree-only, so Euler flattening already solves the problem
  • the real primitive is online path aggregate / path update, so HLD fits better
  • the tree DP is just one child-merge or rerooting pass
  • the tree structure itself changes online

Choose By Signal

Core Invariants

  • every recursive component has a centroid
  • after removing the centroid, every remaining component has size at most half
  • centroid-tree depth is O(log n)
  • every original node has only O(log n) centroid ancestors
  • many standard update/query routes become “walk centroid ancestors and combine”
  • path-counting versions process all paths through the current centroid, then recurse on paths that avoid it

Main Traps

  • confusing the centroid tree with the original rooted tree
  • erasing edges while iterating instead of using removed[]
  • reaching for centroid decomposition when Euler flattening or HLD is the simpler exact fit
  • forgetting to document whether centroid ancestors are stored nearest-first or root-first
  • recomputing distances with an extra LCA factor when the decomposition pass could have stored them already

Exact Starters In This Repo

Reopen Paths