Skip to content

Euler Tour Tree Ladder

This ladder is for the first dynamic-tree lane where the reusable story is:

  • maintain one Euler-tour sequence of a changing forest
  • reroot by rotation
  • cut and link by split/merge
  • answer one subtree-side interval query

It is intentionally a thin lane:

  • one exact starter
  • one flagship verifier-style rep
  • strong compare points back to static subtree flattening, link-cut trees, and split/merge sequence tools

Who This Is For

Use this lane if:

Warm-Up

  • why self-loop tokens carry the vertex values
  • why an edge-oriented subtree is the interval (p, v) ... (v, p) after make_root(p)
  • why rerooting is one sequence rotation, not a DFS rebuild

Target skill:

  • explain why dynamic rooted-subtree queries can still be interval queries if the sequence itself becomes dynamic

Warm-up compare points:

Core

  • represent one tree by self-loops and directed edge tokens
  • make_root(u) by rotation around (u, u)
  • cut(u, v) after rerooting u
  • link(child, parent) by splicing a whole child sequence after (parent, parent)
  • flagship rep: Dynamic Tree Vertex Add Subtree Sum

Target skill:

  • know when the live query is subtree-side enough for ETT and when it has crossed into link-cut territory

Stretch

Target skill:

  • separate the representation trick from the extra monoid or lazy layer that a harder dynamic-tree problem adds later

Retrieval Layer

Repo Anchors And Compare Points

The cleanest in-repo loop here is:

  1. reopen Euler Tour / Subtree Queries until static subtree intervals feel automatic
  2. trust the split/merge instincts from euler-tour-tree-subtree-sum.cpp
  3. solve or revisit Dynamic Tree Vertex Add Subtree Sum
  4. only then jump to lazy subtree updates or sibling dynamic-tree structures

Exit Criteria

You are ready to move on when:

  • you can explain why subtree-side queries belong here instead of in LCT
  • you can derive the subtree interval from the two directed tokens around one edge
  • you can describe make_root, link, and cut as sequence operations
  • you can say exactly what the first repo starter does not support yet

External Practice