Euler Tour (Subtree Flattening)

O(n) build

Number the vertices by DFS entry time so every subtree becomes the contiguous range [tin[u], tout[u]). Subtree queries and updates then reduce to range queries on a Fenwick or segment tree over that order. Iterative, so deep trees are safe.

// use it on

CSES: Subtree Queries ↗

Point updates plus subtree sums: place values at tin[u] in a Fenwick tree and sum the range [tin[u], tout[u]).

// the code

// subtree of u = positions [tin[u], tout[u]) in the visit order
struct EulerTour {
    vector<int> tin, tout, order;
    int timer = 0;
    EulerTour(vector<vector<int>>& adj, int root = 0)
        : tin(adj.size()), tout(adj.size()) {
        vector<pair<int, int>> st = {{root, -1}};
        while (!st.empty()) {
            auto [u, p] = st.back();
            st.pop_back();
            if (u < 0) {  // exit event
                tout[~u] = timer;
                continue;
            }
            tin[u] = timer++;
            order.push_back(u);
            st.push_back({~u, 0});
            for (int v : adj[u])
                if (v != p) st.push_back({v, u});
        }
    }
};

// more tree algorithms

LCA (Binary Lifting)Heavy-Light Decomposition Centroid Decomposition Tree Isomorphism (AHU)