For a path between u and v, increment a counter at u and v. Decrement once at lca(u, v) and once at the parent of the LCA (if it exists). Why?
When you propagate counts upward in the tree (each node adds its count to its parent), the increments at u and v will bubble up to the LCA. The decrement at the LCA keeps the LCA itself counted but prevents the extra count from going higher. The decrement at the parent removes the second extra count.
This is similar to a difference array on a linear range, but adapted for trees. Mark endpoints with , mark the LCA with and its parent with , and let the tree structure propagate the values correctly.
The trick converts O(path length) work per path into O() work per path.