Chapter 8.4: Euler Tour & Tree Flattening

📝 Before You Continue: This chapter requires Chapter 5.3 (trees, tree traversal), Chapter 3.9–3.10 (Segment Trees and Fenwick Trees), and Chapter 8.3 (Tree DP basics). The Euler tour converts tree problems into array problems — you must be comfortable with range query data structures first.

The Euler tour (also called DFS ordering or heavy-light linearization) is a technique that flattens a tree into a linear array. Once flattened, subtree queries become range queries on the array — solvable in O(log N) with a Fenwick tree or segment tree.

This chapter also covers binary lifting for LCA (Lowest Common Ancestor), which solves path queries on trees in O(log N).

Learning objectives:

• Implement DFS-order Euler tour with in/out timestamps
• Use the tour to convert subtree queries into range queries on an array
• Implement binary lifting for LCA computation in O(N log N) preprocessing + O(log N) per query
• Combine Euler tour + LCA to answer path queries efficiently

8.4.0 Motivation: Why Flatten a Tree?

Suppose you have a tree and need to:

• Update all values in the subtree of v
• Query the sum of all values in the subtree of v

With just a DFS, each operation is O(N) in the worst case. But if you can convert the subtree of v into a contiguous array range [in[v], out[v]], you can use a BIT or segment tree for O(log N) per operation.

The Euler tour gives you exactly this: a bijection between subtrees and contiguous ranges.

8.4.1 DFS In/Out Timestamps (Euler Tour)

Assign each vertex two timestamps:

• in[v]: when DFS first visits v ("entry time")
• out[v]: when DFS finishes v's subtree ("exit time")

Key property: Vertex u is in the subtree of v if and only if in[v] ≤ in[u] ≤ out[v].

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<int> adj[MAXN];
int in_time[MAXN], out_time[MAXN];
int order[MAXN];       // order[i] = which vertex was visited i-th
int timer_val = 0;

void dfs(int u, int par) {
    in_time[u] = ++timer_val;   // record entry time
    order[timer_val] = u;        // record vertex at this position

    for (int v : adj[u]) {
        if (v != par)
            dfs(v, u);
    }

    out_time[u] = timer_val;    // record exit time (same or later than in_time)
}

Example:

Tree (rooted at 1):        DFS order:         in/out times:
       1                   visit 1            in[1]=1, out[1]=7
      /|\                  visit 2            in[2]=2, out[2]=4
     2  5  7               visit 4            in[4]=3, out[4]=3
    /|   \                 back to 2          
   4  3   6                visit 3            in[3]=4, out[3]=4
                           back to 1          
                           visit 5            in[5]=5, out[5]=6
                           visit 6            in[6]=6, out[6]=6
                           back to 1          
                           visit 7            in[7]=7, out[7]=7

Subtree of 2 = {2, 4, 3} → range [2, 4]  ✓ (in[2]=2, out[2]=4)
Subtree of 5 = {5, 6}    → range [5, 6]  ✓ (in[5]=5, out[5]=6)
Subtree of 1 = all       → range [1, 7]  ✓ (in[1]=1, out[1]=7)

8.4.2 Subtree Queries with BIT/Segment Tree

Once you have the Euler tour, you can map vertex values to array positions and use a BIT for range queries.

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
vector<int> adj[MAXN];
int in_time[MAXN], out_time[MAXN];
int val[MAXN];       // vertex values
int flat[MAXN];      // flat[i] = val[vertex at position i in Euler tour]
int timer_val = 0;

// ── BIT (Fenwick Tree) for range sum ─────────────────
long long bit[MAXN];
int n;

void bit_update(int i, long long delta) {
    for (; i <= n; i += i & (-i))
        bit[i] += delta;
}

long long bit_query(int i) {
    long long s = 0;
    for (; i > 0; i -= i & (-i))
        s += bit[i];
    return s;
}

long long bit_range(int l, int r) {
    return bit_query(r) - bit_query(l - 1);
}

// ── Euler tour DFS ────────────────────────────────────
void dfs(int u, int par) {
    in_time[u] = ++timer_val;
    flat[timer_val] = val[u];        // place vertex value at its tour position

    for (int v : adj[u]) {
        if (v != par) dfs(v, u);
    }

    out_time[u] = timer_val;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> val[i];

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 0);

    // Build BIT from flat array
    for (int i = 1; i <= n; i++)
        bit_update(i, flat[i]);

    // Example queries:
    // Subtree sum of vertex v:
    int v;
    cin >> v;
    cout << bit_range(in_time[v], out_time[v]) << "\n";

    // Update value of vertex u by delta:
    int u; long long delta;
    cin >> u >> delta;
    bit_update(in_time[u], delta);

    return 0;
}

Complexity:

• Preprocessing: O(N) for DFS + O(N log N) for BIT build
• Subtree query: O(log N)
• Point update (vertex v): O(log N) — update at position in_time[v]
• Subtree update (add delta to all vertices in subtree of v): Use a difference BIT, update at in_time[v] and out_time[v]+1

8.4.3 Lowest Common Ancestor (LCA)

The LCA of two vertices u and v is the deepest vertex that is an ancestor of both.

Tree:          LCA(4, 6) = 2
    1          LCA(4, 7) = 1
   / \         LCA(5, 3) = 2
  2   7
 / \
3   4
   /
  5
  |
  6

LCA has many applications:

• Distance between u and v: dist(u, v) = depth[u] + depth[v] - 2·depth[LCA(u,v)]
• Path queries: queries on the path from u to v can be answered using LCA + Euler tour

Binary Lifting for LCA

Preprocessing: For each vertex v, precompute up[v][k] = the 2^k-th ancestor of v.

up[v][0] = parent(v)         (direct parent)
up[v][1] = parent(parent(v)) (grandparent)
up[v][2] = 2-steps up
...
up[v][k] = up[up[v][k-1]][k-1]

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100001;
const int LOG = 17;  // 2^17 > 10^5

vector<int> adj[MAXN];
int up[MAXN][LOG];   // up[v][k] = 2^k-th ancestor of v
int depth[MAXN];

void dfs(int u, int par, int d) {
    depth[u] = d;
    up[u][0] = par;  // direct parent

    // Fill binary lifting table
    for (int k = 1; k < LOG; k++) {
        up[u][k] = up[up[u][k-1]][k-1];
        // 2^k-th ancestor = 2^(k-1)-th ancestor of 2^(k-1)-th ancestor
    }

    for (int v : adj[u]) {
        if (v != par)
            dfs(v, u, d + 1);
    }
}

// Find LCA of u and v
int lca(int u, int v) {
    // Step 1: bring u and v to the same depth
    if (depth[u] < depth[v]) swap(u, v);
    int diff = depth[u] - depth[v];

    for (int k = 0; k < LOG; k++) {
        if ((diff >> k) & 1)   // if bit k is set in diff
            u = up[u][k];      // jump 2^k steps up
    }

    // Now depth[u] == depth[v]
    if (u == v) return u;      // u was in subtree of v (or vice versa)

    // Step 2: find LCA by binary lifting both simultaneously
    for (int k = LOG - 1; k >= 0; k--) {
        if (up[u][k] != up[v][k]) {  // if ancestors differ, go up
            u = up[u][k];
            v = up[v][k];
        }
    }

    return up[u][0];  // one step above current position = LCA
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // Initialize: root = 1, parent of root = root itself (sentinel)
    up[1][0] = 1;
    dfs(1, 1, 0);

    while (q--) {
        int u, v;
        cin >> u >> v;
        cout << lca(u, v) << "\n";
    }

    return 0;
}

Complexity: O(N log N) preprocessing + O(log N) per LCA query.

Distance Between Two Vertices

int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u, v)];
}

8.4.4 Path Queries with Euler Tour + LCA

Problem: Each vertex has a value. Answer Q queries: "sum of values on the path from u to v."

Approach: Define prefix[v] = sum of values on the path from root to v. Then:

path_sum(u, v) = prefix[u] + prefix[v] - prefix[LCA(u,v)] - prefix[parent(LCA(u,v))]

For dynamic updates (values change over time), this requires a BIT indexed by DFS order — which is exactly the Euler tour.

// path_sum(u, v) using prefix sums + LCA
// Define: prefix[v] = sum of values from root to v (inclusive)
// Then: path_sum(u,v) = prefix[u] + prefix[v] - prefix[lca] - prefix[parent[lca]]

long long path_sum(int u, int v) {
    int l = lca(u, v);
    return prefix[u] + prefix[v] - prefix[l] - prefix[up[l][0]];
    //                                                  ↑ parent of LCA
}

8.4.5 USACO Gold Euler Tour Patterns

Pattern 1: Subtree Update + Query

"Add value x to all vertices in subtree of v. Query sum of all vertices."

Euler tour maps subtree to range [in[v], out[v]]. Use a range-update BIT (lazy propagation or difference array on BIT).

Pattern 2: Path Sum with Updates

"Update vertex v's value. Query sum on path from u to w."

LCA + prefix sums + BIT at DFS positions.

Pattern 3: Euler Tour for LCA-Based Interval

The range [in[u], in[v]] (when in[u] ≤ in[v]) in the Euler tour contains exactly the vertices on the path from u to v (with some extras depending on whether u is an ancestor of v). Used in advanced LCA variants.

8.4.6 Preview: Heavy-Light Decomposition (HLD)

The Euler tour + LCA combination handles most Gold-level tree problems. But there's a class of problems that require range updates AND queries on paths — not just subtrees. For these, the standard Euler tour isn't sufficient.

Heavy-Light Decomposition (HLD) is the Platinum-level technique that handles this. It's worth previewing here since it builds directly on Euler tour concepts.

The Problem HLD Solves

"Given a tree with N vertices, process Q queries of two types:

• update(u, v, delta): add delta to all vertices on the path from u to v
• query(u, v): return the sum of all vertices on the path from u to v"

Euler tour alone can handle subtree updates/queries efficiently, but path queries across the tree require O(log²N) with HLD.

Core Idea

Decompose the tree into heavy chains by always following the "heavy" child (the child with the largest subtree). This guarantees:

• Any root-to-leaf path has at most O(log N) chain switches
• Each chain is a contiguous range in the DFS order
• Path queries = O(log N) range queries on the chains → O(log² N) with segment tree

Heavy child of v = the child c with the largest sz[c]
Heavy path = chain of heavy children from a vertex down to a leaf

Tree:            sz[] values:     Heavy edges (→):
    1  (sz=7)       7
   / \             / \
  2   3 (sz=4)    3   4
 / \ / \         / \ / \
4  5 6  7       1 1 2  1

Heavy children: 1→3 (sz=4 > sz=3), 3→6 (sz=2 > sz=1)
Chains: {1, 3, 6}, {2}, {4}, {5}, {7}

HLD Implementation Sketch (for reference)

// Heavy-Light Decomposition — O(N log N) preprocessing, O(log^2 N) path queries
// Full implementation is Platinum-level; this is a conceptual sketch

int heavy[MAXN];   // heavy[v] = heavy child of v (-1 if leaf)
int head[MAXN];    // head[v] = topmost vertex of v's heavy chain
int pos[MAXN];     // pos[v] = position of v in the HLD flattened array
int cur_pos = 0;

// Step 1: Find heavy children (need sz[] from tree DP first)
void find_heavy(int u, int par) {
    sz[u] = 1;
    heavy[u] = -1;
    int max_sz = 0;
    for (int v : adj[u]) {
        if (v == par) continue;
        find_heavy(v, u);
        sz[u] += sz[v];
        if (sz[v] > max_sz) {
            max_sz = sz[v];
            heavy[u] = v;   // v is the heavy child
        }
    }
}

// Step 2: Assign positions along heavy chains
void decompose(int u, int par, int h) {
    head[u] = h;            // chain head
    pos[u] = cur_pos++;     // position in flattened array

    if (heavy[u] != -1)
        decompose(heavy[u], u, h);      // continue heavy chain

    for (int v : adj[u]) {
        if (v == par || v == heavy[u]) continue;
        decompose(v, u, v);             // start new chain at v
    }
}

// Step 3: Path query using LCA + chain jumping
long long path_query(int u, int v) {
    long long result = 0;
    while (head[u] != head[v]) {
        if (depth[head[u]] < depth[head[v]]) swap(u, v);
        // u's chain head is deeper; query pos[head[u]]..pos[u]
        result += seg_query(pos[head[u]], pos[u]);
        u = parent[head[u]];  // jump to parent of chain head
    }
    // Now u and v are on the same chain
    if (depth[u] > depth[v]) swap(u, v);
    result += seg_query(pos[u], pos[v]);  // query the chain segment
    return result;
}

Complexity:

• Preprocessing: O(N) for find_heavy + O(N) for decompose = O(N)
• Path query: O(log N) chain switches × O(log N) segment tree = O(log² N)

📘 When to use HLD vs Euler tour:

• Subtree queries/updates → Euler tour + BIT (O(log N))
• Path queries/updates, no range update → LCA + prefix sums (O(log N))
• Path range updates + range queries → HLD + segment tree (O(log² N)) ← Platinum

The key takeaway: everything in this chapter (Euler tour, LCA, binary lifting) is the prerequisite for HLD. Once you master Ch.8.4, HLD is a natural extension.

💡 思路陷阱（Pitfall Patterns）

陷阱 1：把"路径查询"误用欧拉序（应用 LCA）

错误判断： "欧拉序把树压成数组，路径查询 u→v 就是 [in[u], in[v]] 区间查询" 实际情况： 欧拉序只保证子树对应连续区间，路径不是连续区间

树：1-2-3-4（链），欧拉序：in[1]=1, in[2]=2, in[3]=3, in[4]=4
查询路径 1→4 看起来是 [1,4]，但路径 2→4 是 [2,4] ——偶然正确
查询路径 3→1（往上走）：in[3]=3, in[1]=1，区间 [1,3] 包含节点 2，
  而 2 不在 3→1 的路径上 ← 错误！

正确方法：path_sum(u,v) = prefix[u] + prefix[v] - prefix[LCA] - prefix[parent(LCA)]

识别信号： 查询涉及两点之间的路径（非子树） → 必须用 LCA 分解，不能直接用 Euler tour 区间

陷阱 2：LCA binary lifting 时 LOG 取值过小

错误判断： "树最多 10⁴ 个节点，LOG=13 够了（2^13=8192 > 10⁴/2）" 实际情况： 需要 2^LOG > N，对于 N=10⁴ 需要 LOG=14（2^14=16384）

// 安全做法：LOG 永远用 ceil(log2(N)) + 1，或直接用 20 覆盖 10^6
const int LOG = 20;  // 2^20 = 1048576，覆盖 N≤10^6 的所有情形
// 不要"精确计算"，用大一点的常数不会影响复杂度

识别信号： LCA 在深链上得到错误答案 → 检查 LOG 是否足够大

⚠️ Common Mistakes

1. Wrong LOG value: For N ≤ 10⁵, use LOG = 17 (since 2^17 = 131072 > 10⁵). For N ≤ 10⁶, use LOG = 20.

2. Root's parent sentinel: The root has no parent. Set up[root][0] = root (points to itself) to avoid going out of bounds when lifting.

3. Off-by-one in Euler tour timer: Start the timer at 1 (not 0) if your BIT is 1-indexed.

4. Wrong path sum formula: Remember to subtract prefix[parent(LCA)], not just prefix[LCA]. The LCA vertex itself is on the path and should be counted once.

5. LCA algorithm assumes tree is rooted: Binary lifting is set up with a fixed root. If the problem doesn't specify a root, choose one (typically vertex 1) and root there.

📋 Chapter Summary

📌 Key Takeaways

❓ FAQ

Q: Is there an O(1) LCA algorithm? A: Yes — RMQ (Range Minimum Query) over a special Euler tour can give O(1) per query after O(N log N) preprocessing. But O(log N) binary lifting is sufficient for USACO Gold.

Q: What if the tree is given as an undirected graph (no specified root)? A: Root at vertex 1. The choice of root doesn't affect LCA correctness, only the depth[] values.

Q: Can I use Euler tour for edge-weighted trees? A: Yes. Assign edge weight to the lower endpoint (child) vertex. Then path queries work the same way, but you use prefix[u] + prefix[v] - 2*prefix[LCA] (not subtracting parent(LCA), since the LCA vertex carries the edge weight to its parent).

🔗 Connections to Later Chapters

• Platinum: Heavy-Light Decomposition (HLD): HLD decomposes the tree into chains, then uses Euler tour + segment tree for O(log² N) path queries with range updates.
• Ch.8.3 (Tree DP): LCA lets you "answer tree DP queries online" — you can handle path queries without offline processing.
• Ch.3.9 (Segment Trees): When BIT doesn't support range updates with lazy propagation, replace BIT with a lazy segment tree.

🏋️ Practice Problems

🟢 Easy

8.4-E1. Subtree Sum Query Given a tree with values at each vertex. Answer Q queries: "What is the sum of values in the subtree of vertex v?"

8.4-E2. LCA Basic Given a tree with N vertices. Answer Q queries: "What is the LCA of u and v?"

🟡 Medium

8.4-M1. Distance Queries Given a tree with N vertices and unit edge weights. Answer Q queries: "What is the distance between vertex u and vertex v?"

8.4-M2. Subtree Update + Query (USACO-style) Given a tree. Process Q operations:

• update v delta: add delta to all vertices in subtree of v
• query v: return the current value of vertex v

🔴 Hard

8.4-H1. Path Query with Updates (USACO Gold difficulty) Given a weighted tree. Process Q operations:

• update u val: set value of vertex u to val
• query u v: sum of values on path from u to v

🏆 Challenge

8.4-C1. Count Paths Passing Through Vertex (Hard) Given a tree. For each vertex v, count the number of paths (u, w) such that v lies on the path from u to w (including u=v or w=v).