Core idea 1 - Paths Through Centroid

Find the centroid $c$. Every path either passes through $c$ or lies entirely within one component after removing $c$. Paths through $c$ can be counted directly. Count paths passing through $c$ 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 $O(\log n)$ because components halve in size, so you process each node $O(\log n)$ times total across all recursion levels.