Read Statement

Read the full problem at the link above. You need to count paths of length exactly $k$, where length is the number of edges. Both endpoints count, so a path from $u$ to $v$ is one path. Constraints make brute force impossible.

With $n$ up to $200,000$, checking all pairs times out. You need a smarter approach that avoids examining every pair. Try to think about how centroids might help before continuing. What paths pass through a centroid?