#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/lowest-common-ancestor-lca/algorithm-counting-paths

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░█████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/graph-theory/lowest-common-ancestor-lca/algorithm-counting-paths

Repovive

Algorithm - Counting Paths - Lowest Common Ancestor (LCA) | Graph Theory | Repovive

Repovive.

Graph Theory37 sections · 1633 units81h total

Open in Course

Algorithm - Counting Paths

(Mark and propagate)

For each path (u, v):

lca_node = lca(u, v)
cnt[u] += 1
cnt[v] += 1
cnt[lca_node] -= 2
if parent[lca_node] exists:
    cnt[parent[lca_node]] -= 0  // or handle separately

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.