Skip to content

Trees And Queries 01

This pack is for rooted-tree retrieval: ancestor jumps, subtree states, rerooting, and path queries in one sitting.

Who This Is For

Use this pack if:

  • tree problems still split in your head into too many separate tricks
  • LCA, tree DP, and HLD each make sense alone but switching between them still feels slow
  • the hard part is deciding what the tree is being used for this time: hierarchy, DP container, or path-query skeleton

Entry Gate

Try this pack only if these already feel like review:

Pack Shape

  • Type: rooted-tree switching drill
  • Topic mix: LCA + tree DP + rerooting + HLD + tree-as-structure reduction
  • Problems: 5
  • Suggested time: 3-4 hours

Topics Under Test

  • deciding whether the tree is mainly an ancestor hierarchy, a DP container, or a path-query structure
  • keeping parent/depth/subtree language stable across different solution families
  • switching from one-root answers to all-roots answers
  • knowing when a tree problem is not “just more DP”

Suggested Order

Slot Problem Topic Why it is here
1 Company Queries II LCA Opens with the cleanest rooted-hierarchy query and anchors depth/ancestor language.
2 Tree Matching Tree DP Switches the tree from a query object into a rooted-subtree DP container.
3 Tree Distances II Rerooting Keeps the rooted-tree vocabulary but changes the main task into all-roots transfer.
4 Path Queries II HLD Reframes the tree again as a path-query reduction over a base array.
5 MTREECOL Tree as precedence structure Optional stretch slot: ends with one tree reduction where the tree is mostly a constraint graph, not a normal DP/query family.

How To Run It

  • solve in order so the pack keeps changing what “the tree” means
  • before coding each slot, write one short line: hierarchy, subtree DP, all-roots DP, path query, or precedence structure
  • if recognition is still fuzzy after about 12-15 minutes, allow one refresher page and restart once
  • if one slot still feels dead after about 30 minutes, log the wrong tree model and continue

Allowed Refreshers

Debrief

After the pack, write down:

  1. Which slot made you choose the wrong tree model first.
  2. Whether you lost more time to state design, ancestor bookkeeping, or path reduction.
  3. Which rooted-tree invariant now feels reusable across several families instead of isolated to one topic.

Go Back Next