Lessons - Difference Arrays on Trees

This problem shows how difference arrays extend to trees. On arrays, you mark range endpoints and propagate with prefix sums. On trees, you mark path endpoints and the LCA, then propagate with DFS. The core idea: a tree path is defined by two endpoints and their LCA.

You can update all nodes on the path in $O(1)$ by marking these three positions. This technique works for any additive path queries: sums, counts, or weights.