Euler Tour / Subtree Queries Ladder

This ladder is for the first tree-query lane where a subtree becomes one array interval and no heavy path machinery is needed.

Who This Is For

Use this lane if:

• rooted-tree ideas already make sense
• subtree language feels stable
• path-query machinery like HLD still feels too heavy for the statement in front of you

Warm-Up

• subtree sizes
• entry times tin / tout
• one DFS order that writes each node once

Good compare points:

• Trees
• Subordinates

Target skill:

• say why a subtree becomes one contiguous interval in single-entry DFS order

Core

• flatten the rooted tree into one entry-order array
• map node u to one position tin[u]
• answer subtree sum/count on [tin[u], tout[u])
• exact flagship rep: Subtree Queries

Target skill:

• know when one subtree query is already just one range query

Stretch

• compare Subtree Queries against Path Queries
• use Distinct Colors as the first "same flattening, different engine" compare point
• move to Heavy-Light Decomposition only when the query leaves the subtree-only world

Target skill:

• distinguish subtree-only flattening from path-query decompositions

Retrieval Layer

• exact quick sheet -> Subtree Queries hot sheet
• exact starter -> euler-tour-subtree.cpp
• tree worldview refresher -> Trees
• lighter range engine compare point -> Fenwick hot sheet

Exit Criteria

You are ready to move on when:

• you can explain why [tin[u], tout[u]) is exactly the subtree of u
• you know when Fenwick is enough after flattening and when you need a segment tree instead
• you can say clearly why HLD is unnecessary for subtree-only queries

External Practice

• CSES - Subtree Queries
• CSES - Path Queries
• CSES - Distinct Colors
• USACO Guide - Euler Tour Technique

Tutorial Link

• Euler Tour / Subtree Queries