Algorithm - Counting Paths

For each path (u, v):

lca_node = lca(u, v)
cnt[u] += 1
cnt[v] += 1
cnt[lca_node] -= 1
if parent[lca_node] exists:
    cnt[parent[lca_node]] -= 1

Then run DFS to propagate: for each node v in post-order, for each child c of v: cnt[v] += cnt[c]. After DFS, cnt[v] holds the number of paths passing through v.

Time: $O(m)$ for marking $m$ paths (assuming $O(1)$ LCA), plus $O(n)$ for DFS. Total: $O(m + n)$. This is much better than the naive $O(m \cdot n)$ approach. Space: $O(n)$ for the cnt array plus $O(n \log n)$ for LCA structures.