You are given a tree with n nodes and m paths. Each path is defined by two nodes (start and end). For each node, count how many paths pass through it. A path connects u to v and passes through every node on the unique route between them. The challenge: how do you efficiently mark all nodes on m different paths?
Naive approach: for each path, walk and increment a counter.
This takes O(m * n) time in the worst case (if paths are long). Better approach: use a marking trick with LCA. Mark path endpoints, then propagate counts using DFS. This reduces the time to O(m + n). The next units explain how.