Find the centroid . Every path either passes through or lies entirely within one component after removing . Paths through can be counted directly. Count paths passing through directly. Then recursively count paths in each component.
This avoids double-counting because paths within components are handled in deeper recursion levels. The recursion depth is because components halve in size, so you process each node times total across all recursion levels.