Skip to content

Euler Tour Tree Hot Sheet

Use this page when the forest changes online and the live question is still one subtree-side view, not one dynamic path query.

Do Not Use When

Choose By Signal

Core Invariants

  • each vertex weight lives only on its self-loop token (u, u)
  • directed edge tokens (u, v) and (v, u) carry 0
  • after make_root(p), the subtree of adjacent child v is exactly the interval from (p, v) to (v, p)
  • make_root(u) is a rotation that makes (u, u) the first token
  • link(child, parent) is one splice after (parent, parent)

Main Traps

  • overclaiming path-query support from a subtree-side starter
  • forgetting to reroot before cut or subtree query
  • double-counting by storing one vertex on multiple tokens
  • mixing static Euler flattening with dynamic Euler tour trees
  • forgetting that the flagship query needs an existing edge (v, p), not an arbitrary root parameter

Exact Starter Route

Reopen Paths