Data Structures19 sections · 729 units
Open in Course

Top Trees

More powerful variant

Top Trees generalize Link-Cut trees:

  • Support path and subtree queries
  • Handle non-local tree queries
  • Cluster-based decomposition

Top Trees can answer queries that neither Link-Cut nor ETT handle efficiently:

  • Path + subtree combination queries
  • Distance oracles
  • Certain dynamic programming on trees

However, Top Trees require roughly 3×3\times more code than Link-Cut trees. For most competitive programming problems, Link-Cut trees or simpler structures suffice.