Euler Tour on Trees

TBH I don’t have a particular definition of it — I just think of it as a tree in the form of an array with indexes. usaco guide says the same — “Flattening a tree into an array to easily query and update subtrees.” that’s all it is.

Why do we actually need euler tour?

lets say you have problems like:

you are given a tree with root 1 (or any root r), you need to answer queries where:

• each node has a value a[i] — add x to all nodes in subtree of u, get sum of subtree of u
• each node has a binary value 1/0 — flip the bits in subtree of u, count the 1’s in subtree of u

similarly there can be many types of queries on subtrees.

lets try to solve this without euler tour first — for each update and query we traverse the subtree and do the operation. with n, q ≤ 1e5, that’s n×q at worst case which is 1e10. too slow.

how do we solve range updates and query problems if it wasn’t a tree? there are data structures that handle range operations on arrays efficiently — segment tree, lazy segment tree, etc.

so what if we just convert the tree into an array (flatten it) and use those? but how do we convert it without losing the structure — without messing up which nodes are in which subtree?

that’s exactly what euler tour solves.

The idea — tin and tout

run a dfs from the root. for every node, record two timestamps:

• tin[v] — the time you enter the node
• tout[v] — the time you exit the node (after its entire subtree is visited)

here’s the key observation: if x is an ancestor of v, the entire visit to v happens while you’re still inside x. meaning:

tin[x] ≤ tin[v] ≤ tout[v] ≤ tout[x]

flip it around — all nodes v whose tin[v] falls in [tin[x], tout[x] - 1] are exactly the nodes in the subtree of x.

so assign each node its tin as its index in the flat array. the subtree of x is now a contiguous range [tin[x], tout[x] - 1]. subtree update = range update. subtree query = range query.

The code

vector<int> tin(n + 1), tout(n + 1);
int timer = 1;

auto dfs = [&](auto &&dfs, int node, int par) -> void {
    tin[node] = timer++;

    for (auto &child : graph[node]) {
        if (child == par) continue;
        dfs(dfs, child, node);
    }

    tout[node] = timer;
};
dfs(dfs, 1, 1);

one thing worth noticing — tout[node] = timer (not timer++). tout is assigned after all children finish, so it’s one past the last tin in the subtree. that’s why the range is [tin[v], tout[v] - 1].

Tracing an example

lets make this concrete. take this tree:

        1
      / | \ \
     2  3   5  7
       /|\
      4  6  10
      |  |
      8  9

dfs from root 1, visiting children in order. here’s what the timestamps look like:

lets verify — subtree of node 3 should contain nodes 3, 4, 8, 6, 9, 10.

range = [tin[3], tout[3] - 1] = [3, 8].

nodes with tin in [3, 8]: node 3 (tin=3), node 4 (tin=4), node 8 (tin=5), node 6 (tin=6), node 9 (tin=7), node 10 (tin=8). ✓

subtree of node 4 = [4, 5] → nodes 4, 8. ✓

subtree of node 9 = [7, 7] → just node 9 (leaf). ✓

The problem — CF 877E

problem link

you’re given a rooted tree with n nodes (root = 1). each node has a light, initially on or off. two types of queries:

• pow v — toggle all lights in the subtree of v
• get v — count how many lights are on in the subtree of v

with euler tour, both become range operations:

• pow v → range flip on [tin[v], tout[v] - 1]
• get v → range sum on [tin[v], tout[v] - 1]

a lazy segment tree handles both. the flip operation is new count = (range size) - (old count), propagated as a lazy toggle bit.

if (s == "pow") {
    st.toggle(tin[x], tout[x] - 1);
} else {
    cout << st.query(tin[x], tout[x] - 1) << "\n";
}

that’s the whole solution once the euler tour is set up.

Full code

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

class SegTree {
    int n;
    vector<int> st, lazy;

    void apply(int p, int l, int r) {
        st[p] = (r - l + 1) - st[p];
        lazy[p] ^= 1;
    }

    void push(int p, int l, int r) {
        if (!lazy[p] || l == r) return;

        int m = (l + r) >> 1;
        apply(p << 1, l, m);
        apply(p << 1 | 1, m + 1, r);
        lazy[p] = 0;
    }

    void upd(int p, int l, int r, int i, int j) {
        if (r < i || j < l) return;

        if (i <= l && r <= j) return apply(p, l, r);

        push(p, l, r);
        int m = (l + r) >> 1;
        upd(p << 1, l, m, i, j);
        upd(p << 1 | 1, m + 1, r, i, j);
        st[p] = st[p << 1] + st[p << 1 | 1];
    }

    int qry(int p, int l, int r, int i, int j) {
        if (r < i || j < l) return 0;

        if (i <= l && r <= j) return st[p];

        push(p, l, r);
        int m = (l + r) >> 1;
        return qry(p << 1, l, m, i, j)
               + qry(p << 1 | 1, m + 1, r, i, j);
    }

public:
    SegTree(int n) : n(n), st(4 * n), lazy(4 * n) {}

    void toggle(int l, int r) { upd(1, 0, n - 1, l, r); }
    int query(int l, int r)   { return qry(1, 0, n - 1, l, r); }
};

void solve() {
    int n;
    cin >> n;
    vector<vector<int>> graph(n + 1);
    vector<int> lights(n + 1);

    for (int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        graph[x].push_back(i);
        graph[i].push_back(x);
    }

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

    vector<int> tin(n + 1), tout(n + 1);
    int timer = 1;

    auto dfs = [&](auto &&dfs, int node, int par) -> void {
        tin[node] = timer++;
        for (auto &child : graph[node]) {
            if (child == par) continue;
            dfs(dfs, child, node);
        }
        tout[node] = timer;
    };
    dfs(dfs, 1, 1);

    SegTree st(n + 1);

    for (int i = 1; i <= n; i++) {
        if (st.query(tin[i], tin[i]) != lights[i])
            st.toggle(tin[i], tin[i]);
    }

    int q;
    cin >> q;

    while (q--) {
        string s;
        cin >> s;
        int x;
        cin >> x;

        if (s == "pow") {
            st.toggle(tin[x], tout[x] - 1);
        } else {
            cout << st.query(tin[x], tout[x] - 1) << "\n";
        }
    }
}

int main() {
    int T = 1;
    while (T--) solve();
}

Complexity

• Preprocessing: O(n) — one dfs
• Per query: O(log n) — lazy seg tree
• Total: O(n + q log n)

Resources

• USACO Guide — Euler Tour
• Codeforces blog on Euler Tour
• CF 877E — problem
• my submission