Walkthrough - Example

Consider a tree: root $1$ with children $2, 3$. Node $2$ has child $4$. Paths: $(4, 3)$ and $(2, 3)$.

The correct formula marks $4$ positions per path: cnt[u] += $1$, cnt[v] += $1$, cnt[lca(u, v)] -= $1$, cnt[parent[lca(u, v)]] -= $1$. The parent decrement stops the path contribution from leaking above the LCA.

Path $(4, 3)$: $lca = 1$. Mark cnt[$4$] += $1$, cnt[$3$] += $1$, cnt[$1$] -= $1$, cnt[parent[$1$]] -= $1$.

Path $(2, 3)$: $lca = 1$. Mark cnt[$2$] += $1$, cnt[$3$] += $1$, cnt[$1$] -= $1$, cnt[parent[$1$]] -= $1$.

After DFS propagation, each node's count reflects how many paths pass through it. Test your code to make sure the LCA adjustment is correct.