Euler Tour Technique

The Euler tour technique converts subtree queries to range queries. Perform a DFS and record each node when you enter and exit.

A node $v$'s subtree corresponds to a contiguous range in this tour. Store $tin[v]$ (entry time) and $tout[v]$ (exit time).

The subtree of $v$ contains exactly nodes with entry times in $[tin[v], tout[v]]$. Now subtree sum, subtree min, and similar queries become range queries on an array.

Use a segment tree or Fenwick tree on the tour. Time: $O(\log n)$. Space: $O(n)$.