iv. Euler Tour, Subtree and Path Queries

Flatten the tree in DFS preorder: the subtree of $u$ becomes the interval $[{\text{tin}}_u,{\text{tout}}_u)$, so every array structure (Fenwick, lazy segment tree, persistent tree, Mo) works on subtrees. Paths are not intervals, but root paths are recovered with entry/exit tricks and LCA (LCA); general path updates and queries go to HLD.

struct EulerTour {                                         // subtree(u) = [tin[u], tout[u]) in preorder
    int n; vector<int> tin, tout, order, par, dep; vector<vector<int>> ch;   // ch[u] in tin order
    EulerTour(const vector<vector<int>>& adj, int root) : n(sz(adj)), tin(n), tout(n), par(n, -1), dep(n), ch(n) {
        vector<int> it(n), st{root}; order = {root};
        while (sz(st)) {
            int u = st.back();
            if (it[u] < sz(adj[u])) {
                int v = adj[u][it[u]++]; if (v == par[u]) continue;
                par[v] = u, dep[v] = dep[u] + 1, tin[v] = sz(order), order.push_back(v), ch[u].push_back(v), st.push_back(v);
            } else tout[u] = sz(order), st.pop_back();
        }
    }
    bool isAnc(int u, int v) const { return tin[u] <= tin[v] && tout[v] <= tout[u]; }   // u ancestor of v (or equal)
    int childToward(int u, int v) const {                  // child of u whose subtree contains v (u a proper ancestor)
        return *prev(upper_bound(all(ch[u]), v, [&](int x, int c) { return tin[x] < tin[c]; }));
    }
};

Proof: subtrees are intervals

The DFS enters $u$, then visits exactly the vertices of $u$‘s subtree before leaving $u$ (it only moves to children and returns to parents), and every vertex gets the next preorder index when entered. So the subtree occupies the consecutive indices ${\text{tin}}_u,\dots ,{\text{tout}}_u-1$. Ancestry is interval containment. The children of $u$ get increasing tin in the order visited, and their intervals partition $({\text{tin}}_u,{\text{tout}}_u)$, so the child containing $v$ is the last one with $\text{tin}\le {\text{tin}}_v$.

Reductions

Operation	Array form
point update, subtree sum	Fenwick at tin, range sum $[{\text{tin}}_u,{\text{tout}}_u)$ (CSES “Subtree Queries”)
subtree add, point value	range add / point query (difference Fenwick)
subtree add, subtree sum / max	lazy segment tree
root-path sum $S(u)$ with point updates	subtree add of $x$ at $v$‘s interval; $S(u)$ = point query at ${\text{tin}}_u$
path sum $u$–$v$	$S(u)+S(v)-2S(\ell )+a_{\ell }$ with $\ell =\text{lca}$ (any group: xor, sums mod $p$)
path XOR $u$–$v$	$S(u)\oplus S(v)\oplus a_{\ell }$ — the "$-2S(\ell )$" term is XOR-ing $S(\ell )$ twice, which is already free (any value XORed with itself cancels), so only the $+a_{\ell }$ survives
path add, point query	difference on the tree: $+x$ at $u,v$; $-x$ at $\ell$ and $\text{par}(\ell )$; value = subtree sum (edge-weight variant with the weight pushed to the child endpoint: see tree difference array)
path add, subtree sum	two Fenwicks (below)
entry $+a$, exit $-a$ tour (size $2n$)	prefix up to ${\text{in}}_u$ = root path; Mo’s on trees (Mo’s Algorithm): map each query to the array range $[{\text{in}}_u,{\text{in}}_v]$ (or $[{\text{out}}_u,{\text{in}}_v]$ plus the LCA, when $u$ is not an ancestor of $v$), then run Mo’s with a toggle instead of add/remove — the first time the pointer crosses a vertex, activate it (e.g. add its colour to a frequency map); the second time (its exit), deactivate it; every vertex off the path is toggled on then off and vanishes, exactly simulating the path
vertices at depth $d$ in subtree($u$)	per-depth sorted tin lists, two binary searches
$k$-th smallest in a subtree	persistent segment tree over the preorder array
subtree of $u$ after rerooting at $r$	whole tree, or the complement of the child-toward-$r$ interval
distinct colours in a subtree	offline over intervals (Offline 2D Queries) or small-to-large

struct PathAddSubtreeSum {                                 // add x on path u - v; sum of a subtree
    const EulerTour& T; Fenwick<ll> A, B;                  // A: c(z), B: c(z) * (dep z + 1)
    PathAddSubtreeSum(const EulerTour& T) : T(T), A(T.n), B(T.n) {}
    void point(int z, ll c) { if (z < 0) return; A.add(T.tin[z], c); B.add(T.tin[z], c * (T.dep[z] + 1)); }
    void pathAdd(int u, int v, int l, ll x) { point(u, x); point(v, x); point(l, -x); point(T.par[l], -x); }   // l = lca(u, v)
    ll subtreeSum(int w) const { return B.sum(T.tin[w], T.tout[w]) - (ll)T.dep[w] * A.sum(T.tin[w], T.tout[w]); }
};
vector<pair<int, int>> rerootedSubtree(const EulerTour& T, int u, int r) {   // subtree of u when rooted at r, as intervals
    if (u == r) return {{0, T.n}};
    if (!T.isAnc(u, r)) return {{T.tin[u], T.tout[u]}};
    int c = T.childToward(u, r);
    return {{0, T.tin[c]}, {T.tout[c], T.n}};
}
int countAtDepth(const EulerTour& T, const vector<vector<int>>& byDep, int u, int d) {   // byDep[d]: sorted tins
    if (d >= sz(byDep)) return 0;
    auto& v = byDep[d];
    return int(lower_bound(all(v), T.tout[u]) - lower_bound(all(v), T.tin[u]));
}

Proof: the path and reroot formulas

Root paths: adding $x$ to the interval of $v$‘s subtree adds $x$ to $S(u)$ exactly for $u$ in that subtree, i.e. those whose root path contains $v$. Path sum: $S(u)+S(v)$ counts the common part above $\ell$ twice and $\ell$ itself twice; subtracting $2S(\ell )$ removes the common part and $\ell$, and $+a_{\ell }$ puts $\ell$ back. Difference trick: the value at $y$ is ${\sum }_{z\in \text{sub}(y)}c(z)$; $y$ on the path gets $x$ ($y$‘s subtree holds one or two of $u,v$ and, when it holds both, also $\ell$, plus $\text{par}(\ell )$ never), and $y$ off the path gets 0. Path add, subtree sum: ${\sum }_{y\in \text{sub}(w)}{\sum }_{z\in \text{sub}(y)}c(z)={\sum }_{z\in \text{sub}(w)}c(z)({\text{dep}}_z-{\text{dep}}_w+1)$, since $z$ is counted once for each $y$ between $w$ and $z$; split into the two Fenwicks. Reroot: with root $r$, the subtree of $u$ is everything hanging off $u$ away from $r$. If $r$ is outside $u$‘s original subtree, that is the original subtree; if $r$ is inside, below child $c$, it is everything except $c$‘s original subtree; if $r=u$, everything. Depth count: vertices at depth $d$ in $u$‘s subtree are those at depth $d$ with tin in $[{\text{tin}}_u,{\text{tout}}_u)$.

The three tours

Tour	Length	Gives
preorder tin/tout	$n$	subtree intervals, ancestry test
entry and exit events	$2n$	root-path sums by $\pm$ (exit cancels entry), Mo on trees, bracket encoding of the tree shape
Euler walk (vertex after each child)	$2n-1$	LCA by depth RMQ, dynamic diameter (Tree Basics), Euler tour trees

Dynamic versions: keep the walk in a balanced BST to support link/cut with subtree aggregates (Euler Tour Tree).

Entry/exit cancellation needs an invertible operation

The $2n$ tour’s “side branches cancel” trick relies on being able to undo a value (sum, XOR) when exiting a subtree. It does not work for max, min, matrix products, or string concatenation — there is no way to “un-max” a value once a branch has been explored and left. For a path query on a non-invertible operation, abandon this tour and build HLD instead.