Euler Tour Technique — Subtree Queries on Trees

The tour

int[] enter, exit_;
int time = 0;
void dfs(int u) {
  enter[u] = time++;
  for (int v : children[u]) dfs(v);
  exit_[u] = time;  // exclusive end
}

Subtree sum

Range [enter[v], exit[v]) in tour = all nodes in subtree of v. Use segment tree or BIT.

LCA via Euler tour

Euler tour with depths + range min. LCA(u, v) = node with min depth in range between u's and v's occurrences.

Space

O(N) for tour + auxiliary DS. Same as tree size.