Departments and Budgets — Solution & Editorial

Back to the Problem

Euler tour flattening: a subtree becomes the contiguous interval [tin, tout], so a Fenwick tree over the tour order answers subtree sums with point updates.

Complexity: O((N + Q) log N)