Challenge: Tree DP with Queries

What if you need to answer many queries like "what's the answer if we root at node $q$"? Naive: $O(n)$ per query = $O(nq)$ total. With rerooting: $O(n)$ preprocessing, $O(1)$ per query. Precompute answers for all nodes with rerooting. Store in an array. Answer queries by lookup.

This pattern works for any associative operation on subtrees. The key is making the "reroot" operation O($1$). This is a useful technique for turning O(nq) into O(n + q). Precomputation pays off with many queries.